Best Time to Buy and Sell Stock with Transaction Fee

Read the rules literally and recurse over the days with a single boolean for whether a share is held. Each day offers two branches: do nothing, or act. When flat, acting is a buy that spends prices[day]; when holding, acting is a sale that earns prices[day] - fee. The answer is the best branch starting flat before day 0.

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
            # Option 1: do nothing today and move on.
            outcome = best(day + 1, holding)
            if holding:
                # Option 2: sell today; the fee is charged on this sale.
                outcome = max(outcome, prices[day] - fee + best(day + 1, False))
            else:
                # Option 2: buy today and start holding.
                outcome = max(outcome, -prices[day] + best(day + 1, True))
            return outcome

        return best(0, False)

Why it is exponential: each day doubles the number of branches, so the tree has about 2^n leaves and the running time is O(2^n). Only the recursion stack is used for space, O(n) deep. For prices.length up to 5 * 10^4 this is hopeless, and the same (day, holding) state is recomputed by countless paths — the classic signal that the states should be named and reused.

A different angle: keep hold as the effective cost of the share you would be holding. If the market drops below hold, the cheapest entry improves, so lower hold. If today’s price clears hold + fee, a sale is profitable: bank price - hold - fee and reset hold to price - fee. The reset lets a continuing rise be harvested again later while still paying the fee only once for the whole run.

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        cash = 0
        hold = prices[0]
        for price in prices[1:]:
            if price < hold:
                # A cheaper entry replaces the current basis.
                hold = price
            elif price > hold + fee:
                # Sell: bank the profit after the fee, then re-arm the basis.
                cash += price - hold - fee
                hold = price - fee
        return cash

Why it works: the reset hold = price - fee is the trick. If the price later climbs to q, the next sale adds q - (price - fee) - fee = q - price, so the two sales together earn q - original_hold - fee — exactly one transaction from the original entry to q with the fee paid once. Resetting therefore merges an advancing sale into the trade that opened it instead of starting a fresh transaction, and lowering hold on a dip finds the best basis. Every elif sale strictly increases the total, so the scan is optimal.

Complexity: one pass over the array with two scalar variables, so O(n) time and O(1) space. The fee comparison price > hold + fee is the only extra cost, and it guarantees each banked trade is genuinely profitable.

Name the two situations the brute force kept rediscovering. Let flat be the best profit achievable through the current day while owning no share, and hold the best profit while owning one. Each new day updates both from yesterday’s pair:

• flat = max(flat, hold + price - fee) — either stay flat, or sell the share held and pay the fee.
• hold = max(hold, flat - price) — either keep the share, or buy one using the flat cash.

The two assignments read the old values, so they are computed together (in Python the parallel assignment f0, f1 = ... does this). The answer after the last day is flat, because any optimal strategy is better off having sold everything.

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        # f0: best profit while flat; f1: best profit while holding a share.
        f0, f1 = 0, -prices[0]
        for x in prices[1:]:
            f0, f1 = max(f0, f1 + x - fee), max(f1, f0 - x)
        return f0

Why it is optimal: the pair (day, holding) is a complete state — the future depends only on whether a share is held and the best profit so far — so the recurrence is a correct dynamic program. Each day does constant work, giving O(n) time, and only the two previous values are ever live, giving O(1) space. This is the generalizable form: adding a cooldown or a transaction cap changes the recurrence, not the structure.

Watch the two states update day by day — which candidate wins each transition, and exactly where the fee is subtracted: