Best Time to Buy and Sell Stock with Transaction Fee

Problem

You are given prices, where prices[i] is the price of a stock on day i, and an integer fee. You may complete as many transactions as you like (buy then sell), but:

• you can hold at most one share at a time (you must sell before buying again), and
• each completed transaction charges fee (count it once per buy-sell round trip — e.g. on the sell).

Return the maximum profit achievable.

Examples

• prices = [1, 3, 2, 8, 4, 9], fee = 2 → 8 — buy at 1, sell at 8 (profit 8-1-2 = 5); buy at 4, sell at 9 (profit 9-4-2 = 3); total 8.
• prices = [1, 3, 7, 5, 10, 3], fee = 3 → 6 — buy at 1, sell at 10 (profit 10-1-3 = 6); a single big transaction beats splitting once the fee is charged twice.
• prices = [1, 2, 3], fee = 5 → 0 — no round trip clears the fee, so do nothing.

Constraints

• 1 <= prices.length <= 5 * 10^4
• 1 <= prices[i] < 5 * 10^4
• 0 <= fee < 5 * 10^4

With n up to 5·10^4, an O(n) sweep is expected; anything exponential in the number of transactions is hopeless.

Think about it first

TL;DR

Two-state machine — hold vs. cash — swept once with rolling scalars: O(n) time, O(1) space.

The recurrence

For each day i, track the best profit in two states:

• hold(i) = best profit if, after day i, you own a share.
• cash(i) = best profit if, after day i, you own nothing.

hold(i) = max(hold(i-1),  cash(i-1) - prices[i])          # keep, or buy today
cash(i) = max(cash(i-1),  hold(i-1) + prices[i] - fee)    # keep, or sell today
hold(0) = -prices[0]
cash(0) = 0
answer  = cash(n-1)

Charging fee on the sell (inside cash) counts it exactly once per completed round trip.

Approach 1 — Brute-force recursion

The insight (baseline): at each day, in each state, branch on the allowed actions. A helper (day, holding) explores keep / buy / sell.

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        n = len(prices)
        def best(day: int, holding: bool) -> int:
            if day == n:
                return 0
            skip = best(day + 1, holding)
            if holding:
                sell = prices[day] - fee + best(day + 1, False)
                return max(skip, sell)
            buy = -prices[day] + best(day + 1, True)
            return max(skip, buy)
        return best(0, False)

Complexity: O(2^n) time, O(n) stack.

Why the constraints kill it: every day doubles the branch count; at n = 5·10^4 this is unimaginably large. The same (day, holding) pairs are recomputed endlessly.

Approach 2 — Top-down memoization

The insight: the state is just (day, holding) — only 2n combinations. Cache them.

from functools import cache

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        n = len(prices)
        @cache
        def best(day: int, holding: bool) -> int:
            if day == n:
                return 0
            skip = best(day + 1, holding)
            if holding:
                return max(skip, prices[day] - fee + best(day + 1, False))
            return max(skip, -prices[day] + best(day + 1, True))
        return best(0, False)

Complexity: O(n) time, O(n) space (cache + stack).

Approach 3 — Bottom-up tabulation

The insight: fill two arrays hold and cash from day 0 forward; each day depends only on the previous day.

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        n = len(prices)
        hold = [0] * n
        cash = [0] * n
        hold[0] = -prices[0]
        for i in range(1, n):
            hold[i] = max(hold[i - 1], cash[i - 1] - prices[i])
            cash[i] = max(cash[i - 1], hold[i - 1] + prices[i] - fee)
        return cash[n - 1]

Complexity: O(n) time, O(n) space.

Approach 4 — Space-optimized (two rolling scalars)

The insight: each day reads only yesterday’s hold and cash, so two numbers replace both arrays.

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        hold = -prices[0]                 # bought on day 0
        cash = 0
        for price in prices[1:]:
            hold = max(hold, cash - price)
            cash = max(cash, hold + price - fee)
        return cash

Walkthrough (prices = [1, 3, 2, 8, 4, 9], fee = 2), tracking (hold, cash):

Return cash = 8. ✓ (Note that at day 5 hold was updated before cash, so selling can reuse today’s cheap re-buy — which is fine, since buying and selling on the same day nets only -fee ≤ 0 and never helps.)

Complexity: O(n) time, O(1) space.

Common pitfalls

• Charging the fee on both buy and sell. Pick one side (here, the sell). Double-charging halves your profit on every trade.
• Returning max(hold, cash) at the end. Ending while still holding a share is never optimal — cash already dominates. Return cash.
• Update order within a day. Updating hold first, then cash, lets cash momentarily “sell” a share bought the same day; this is harmless (same-day buy+sell loses the fee) but be sure it can’t be forced. If in doubt, compute both from the old values with a temp.
• Overflow-style thinking. No overflow in Python, but seeding hold = 0 instead of -prices[0] silently allows a free first share.

Pattern takeaway

When a problem has a small, fixed set of “modes” you can be in (holding vs. not), model it as a state machine and keep one DP value per state, transitioning day by day. This “hold/cash” pair generalizes across the whole Best-Time-to-Buy-and-Sell family; adding constraints (a cooldown, a transaction cap, a fee) just adds or reweights transitions. As always, if each step reads only the previous step, collapse the arrays to one scalar per state.