Best Time to Buy and Sell Stock with Transaction Fee — Solution

Problem

You have a list of daily stock prices and must pay a fixed fee each time you complete a sale. You can buy and sell as many times as you want — but you can only hold one share at a time — and you want to maximize total profit after fees.

• Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
• Output: 8
• Explanation: Buy at 1 and sell at 8 (profit 8 − 1 − 2 = 5), then buy at 4 and sell at 9 (profit 9 − 4 − 2 = 3).

Intuition

On any given day you're in exactly one of two states: holding a share or not. The fee discourages selling for small gains, so the decision isn't "sell whenever price goes up" — you need to clear the fee threshold. Tracking just these two states and their best possible profit lets you scan the prices once and make the right choice at every step.

Solution — DP State Machine

Maintain two values through the price list: cash (best profit when you're not holding a share) and held (best profit when you are holding one). Each day, update both by considering whether to act or do nothing.

1. Initialize cash = 0 (no share, no profit yet) and held = -prices[0] (bought on day 0).
2. For each subsequent price, compute a temporary copy of the old cash before overwriting it.
3. Update cash: either stay out of the market, or sell today (held + price − fee).
4. Update held: either keep holding, or buy today using the old cash (prev_cash − price).
5. Return cash — you never want to end while holding a share.

1def maxProfit(prices, fee):
2    cash = 0               # best profit while not holding a share
3    held = -prices[0]      # best profit while holding a share (bought day 0)
4
5    for price in prices[1:]:
6        prev_cash = cash
7        cash = max(cash, held + price - fee)   # sell today or stay out
8        held = max(held, prev_cash - price)    # buy today or keep holding
9
10    return cash

Time: O(n) — one pass through the prices array.
Space: O(1) — only two integer variables regardless of input size.

Complexity Summary

Common Mistakes

• Not saving the old cash before updating it — if you compute the new cash and immediately use it to compute held, you allow buying and selling on the same day (which this problem prohibits). Save prev_cash first.
• Charging the fee on both buy and sell — the fee is one flat cost per completed transaction; applying it twice doubles the penalty and produces the wrong answer.
• Using the no-fee greedy ("collect every upward slope") — without a fee that strategy is correct, but the fee changes the break-even point; small profitable moves become net losses once the fee is applied.
• Initializing held = 0 instead of held = -prices[0] — buying always costs money; starting held at 0 pretends the first purchase was free, which inflates every subsequent profit calculation.
• Trying to enumerate buy/sell day pairs explicitly — the number of valid pairs is exponential; the state machine collapses that to a single linear scan by encoding all possible histories into two values.

Related Problems

• Best Time to Buy and Sell Stock — single transaction only; no fee and no state machine needed
• Best Time to Buy and Sell Stock II — unlimited transactions, no fee; simpler greedy suffices
• Best Time to Buy and Sell Stock III — at most two transactions; same state-machine idea with more states
• Best Time to Buy and Sell Stock with Cooldown — unlimited transactions but a one-day cooldown after selling; adds a third state to the machine
• House Robber — canonical two-state DP where each step chooses between acting or skipping, the same structural pattern as cash/held