Code Implementation

class Solution:
    def maxProfit(self, prices, fee):
        if not prices:
            return 0
        n = len(prices)
        hold = -prices[0]
        cash = 0
        for price in prices[1:]:
            prev_cash = cash
            # If we sell today: add price, subtract fee
            cash = max(cash, hold + price - fee)
            # If we buy today: subtract price from cash
            hold = max(hold, prev_cash - price)
        return cash
      

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if (prices.empty()) return 0;
        int n = prices.size();
        int hold = -prices[0];
        int cash = 0;
        for (int i = 1; i < n; ++i) {
            int prev_cash = cash;
            cash = max(cash, hold + prices[i] - fee);
            hold = max(hold, prev_cash - prices[i]);
        }
        return cash;
    }
};
      

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices.length == 0) return 0;
        int n = prices.length;
        int hold = -prices[0];
        int cash = 0;
        for (int i = 1; i < n; i++) {
            int prevCash = cash;
            cash = Math.max(cash, hold + prices[i] - fee);
            hold = Math.max(hold, prevCash - prices[i]);
        }
        return cash;
    }
}
      

var maxProfit = function(prices, fee) {
    if (!prices.length) return 0;
    let hold = -prices[0];
    let cash = 0;
    for (let i = 1; i < prices.length; i++) {
        let prevCash = cash;
        cash = Math.max(cash, hold + prices[i] - fee);
        hold = Math.max(hold, prevCash - prices[i]);
    }
    return cash;
};
      

Problem Description

You are given an array prices where prices[i] represents the price of a stock on the i-th day, and an integer fee representing a transaction fee for each buy or sell operation.

You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times), but you must pay the transaction fee each time you sell the stock. You cannot hold more than one share of the stock at a time (i.e., you must sell the stock before you buy again).

Return the maximum profit you can achieve.

• Each transaction consists of buying and then selling the stock.
• You must pay the fee only when you sell.
• You cannot buy again before selling your current stock.
• There is always at least one valid solution (possibly zero profit).

Thought Process

At first glance, it might seem reasonable to try every possible combination of buys and sells to maximize profit, but this brute-force approach is not feasible for large inputs due to exponential complexity.

Instead, we can think about the problem as a sequence of decisions: on each day, should we buy, sell, or hold? Since we cannot hold more than one stock at a time, our state can be described by whether we are currently holding a stock or not.

We need to keep track of two scenarios for each day:

• Holding a stock: What's the maximum profit if we have a stock at the end of day i?
• Not holding a stock: What's the maximum profit if we don't have a stock at the end of day i?

Solution Approach

• Dynamic Programming States:
  • hold: The maximum profit achievable at day i if we are currently holding a stock.
  • cash: The maximum profit achievable at day i if we are not holding a stock.
• Initialization:
  • On day 0, if we buy the stock, our profit is -prices[0] (since we spent money).
  • If we do nothing, our profit is 0.
• Transitions:
  • For each day i from 1 to n-1:
    • To compute cash: Either we did nothing (cash stays the same), or we sell today (add today's price, subtract fee, and add to yesterday's hold).
    • To compute hold: Either we did nothing (hold stays the same), or we buy today (subtract today's price from yesterday's cash).
• Result:
  • At the end, the answer is cash, since holding a stock can't count as profit until it's sold.

This approach only needs two variables and a single pass through the array, making it efficient and elegant.

Example Walkthrough

Let's use prices = [1, 3, 2, 8, 4, 9] and fee = 2.

• Day 0: Buy at 1. hold = -1, cash = 0
• Day 1: Price is 3.
  • Sell: hold + 3 - 2 = -1 + 3 - 2 = 0 → cash = max(0, 0) = 0
  • Buy: cash - 3 = 0 - 3 = -3 → hold = max(-1, -3) = -1
• Day 2: Price is 2.
  • Sell: hold + 2 - 2 = -1 + 2 - 2 = -1 → cash = max(0, -1) = 0
  • Buy: cash - 2 = 0 - 2 = -2 → hold = max(-1, -2) = -1
• Day 3: Price is 8.
  • Sell: hold + 8 - 2 = -1 + 8 - 2 = 5 → cash = max(0, 5) = 5
  • Buy: cash - 8 = 0 - 8 = -8 → hold = max(-1, -8) = -1
• Day 4: Price is 4.
  • Sell: hold + 4 - 2 = -1 + 4 - 2 = 1 → cash = max(5, 1) = 5
  • Buy: cash - 4 = 5 - 4 = 1 → hold = max(-1, 1) = 1
• Day 5: Price is 9.
  • Sell: hold + 9 - 2 = 1 + 9 - 2 = 8 → cash = max(5, 8) = 8
  • Buy: cash - 9 = 5 - 9 = -4 → hold = max(1, -4) = 1

Final answer: cash = 8. We can achieve a maximum profit of 8.

Time and Space Complexity

• Brute-force approach:
  • Would try all possible buy/sell combinations, leading to exponential time complexity: O(2^n).
  • Space complexity would also be high due to recursion stack.
• Optimized DP approach:
  • We only loop through n days, updating two variables: O(n) time.
  • Only two variables are needed: O(1) space.

This efficiency comes from reducing the problem to a simple state machine, tracking only the essential information.

Summary

The "Best Time to Buy and Sell Stock with Transaction Fee" problem can be efficiently solved using a dynamic programming approach that keeps track of two states: holding and not holding a stock. By updating these states with each day's price and considering the transaction fee only when selling, we can find the maximum profit in a single pass with constant space. The elegance of this solution lies in its simplicity and efficiency, making it well-suited for large input sizes.