Best Time to Buy and Sell Stock, in depth: one state machine for all six variants, a correctness argument, trade reconstruction and the k-transaction shortcut

The problem family

All variants share one model: a list of daily prices, one share at most at a time, a buy and a later sell form one transaction, and you must sell before you buy again. They differ in a single rule.

Variant III is just IV with k equal to 2, and II is IV with k large enough never to bind. So the real content is one recurrence plus two small modifications.

States and transitions

Define two numbers for every transaction budget j from 1 to k. free[j] is the most cash you can have at the end of today while holding nothing, having completed at most j sells. hold[j] is the most cash you can have while holding one share bought as your j-th purchase. Cash starts at zero and goes negative when you buy, so a holding state is a debt that a later sale repays.

Each day, each state has two ways in. You can rest: tomorrow's free[j] may simply equal today's. Or you can act: sell the share you hold (hold[j] + price) or buy using the cash from a state with one fewer completed transaction (free[j-1] - price). The DP takes the maximum of the two ways in. Charging the transaction on the buy rather than the sell is a convention; either works if you are consistent, and charging on the buy makes free[0] = 0 a natural base case.

At most k transactions

Here is the general version. It is short enough to memorise, and the two lines worth staring at are the loop direction and the shortcut at the top.

NEG = float("-inf")

def max_profit_k(prices, k):
    """At most k buy-sell pairs, one share at a time. O(n*k) time, O(k) space."""
    n = len(prices)
    if n < 2 or k == 0:
        return 0
    if k >= n // 2:                      # budget can never bind: take every rise
        return sum(max(0, b - a) for a, b in zip(prices, prices[1:]))
    hold = [NEG] * (k + 1)               # hold[j]: best cash holding a share, j-th buy made
    free = [0] * (k + 1)                 # free[j]: best cash with no share, j sells made
    for x in prices:
        for j in range(k, 0, -1):        # downward: free[j-1] is still yesterday's value
            free[j] = max(free[j], hold[j] + x)
            hold[j] = max(hold[j], free[j - 1] - x)
    return free[k]

The shortcut matters because a profitable transaction needs at least two days, so no schedule can use more than n/2 of them. Once k reaches that, the budget never binds and the answer is the sum of every positive day-to-day rise, which is variant II. Without the shortcut, a caller passing k equal to a billion allocates two arrays of a billion entries.

The downward loop over j is the subtle part. Updating hold[j] reads free[j-1]. If j ran upward, free[j-1] would already hold today's value, which might include selling today, so the code would sell and rebuy on the same day and count it as two transactions. That is harmless for profit in this variant (a same-day sell and rebuy nets zero, and with a fee it only loses money, so the max never picks it), but it silently breaks the cooldown variant and any rule that forbids acting twice on one day, so keep the order that is right for all of them.

Worked example by hand

Take prices [3, 3, 5, 0, 0, 3, 1, 4] and k = 2. The table shows the four state values at the end of each day, after the update.

Read it as a story. On day 2 the first transaction can lock in a profit of 2 (buy at 3, sell at 5), so free[1] becomes 2. On day 3 the price drops to 0, and hold[2] jumps to 2: spend nothing on a second share while keeping the profit of 2 already banked. On day 7, selling that share at 4 gives free[2] = 6. Notice also that hold[1] moved to 0 on day 3 and free[1] ends at 4, the best single trade (buy at 0, sell at 4). With an unlimited budget the same series gives 8: 2 + 3 + 3, every rise collected separately. The difference between 6 and 8 is the cost of the budget.

Cooldown, fees and the single trade

The other variants each change one thing in the machine.

def max_profit_one(prices):              # variant I: k = 1
    best, low = 0, float("inf")
    for x in prices:
        low = min(low, x)
        best = max(best, x - low)
    return best

def max_profit_cooldown(prices):         # sell today, cannot buy tomorrow
    hold, sold, rest = float("-inf"), 0, 0
    for x in prices:
        hold, sold, rest = max(hold, rest - x), hold + x, max(rest, sold)
    return max(sold, rest)

def max_profit_fee(prices, fee):         # unlimited trades, fee charged once per sell
    hold, free = float("-inf"), 0
    for x in prices:
        hold, free = max(hold, free - x), max(free, hold + x - fee)
    return free

Variant I collapses to a running minimum: the best single trade ending today is today's price minus the cheapest earlier price. For cooldown, a sale moves you into a third state, sold, which can only flow into rest the next day, and buying reads from rest, never from sold. The tuple assignment is the important detail: all three right-hand sides must read yesterday's values. On [1, 2, 3, 0, 2] the answer is 3: buy 1, sell 2, cool down, buy 0, sell 2.

For fees, subtract the fee on exactly one edge of the transaction. On [1, 3, 2, 8, 4, 9] with fee 2 the answer is 8: buy 1 sell 8 nets 5, buy 4 sell 9 nets 3. Notice the machine declines the small rise from 2 to 3 inside the first run, because two short trades would pay the fee twice. That is the whole value of modelling the fee in the state rather than post-processing greedy trades.

Why the recurrence is correct

Why is the max-of-two-predecessors recurrence enough? Use the principle of optimality on schedules. Any valid schedule, read up to day d, ends in one specific state: holding or not, with some number of completed purchases. Its cash at that point equals its cash at day d-1 plus the effect of today's single action (nothing, buy or sell). So the best cash over all schedules ending in state S on day d is the best, over each predecessor state, of the best cash there plus the action's effect. Nothing else about the past affects the future: tomorrow's options depend only on whether you hold a share and how many transactions remain. This is the Markov property that makes DP valid, and it is exactly what fails if you add a rule like a minimum holding period of three days, which you would fix by adding states that record days held.

The k >= n/2 shortcut has its own short proof. Split the price series into maximal rising runs. One transaction per run, buying at the run's start and selling at its end, collects every positive rise, and there are at most n/2 such runs. No schedule can beat the sum of positive rises, because any transaction's profit is a telescoping sum of daily changes that can only be smaller once negative days are included.

Recovering the trades

Interviews ask for the number; a backtest or an audit trail needs the trades. Keep the full table of states per day and walk back from the final state, asking at each step which term of the max produced the value.

def trades_k(prices, k):
    """Return (profit, [(buy_day, sell_day), ...]) for at most k transactions."""
    n, NEG = len(prices), float("-inf")
    free = [[0] * (k + 1) for _ in range(n + 1)]     # free[d][j] after d days
    hold = [[NEG] * (k + 1) for _ in range(n + 1)]
    for d in range(1, n + 1):
        x = prices[d - 1]
        for j in range(1, k + 1):
            free[d][j] = max(free[d - 1][j], hold[d - 1][j] + x)
            hold[d][j] = max(hold[d - 1][j], free[d - 1][j - 1] - x)
    out, d, j, holding = [], n, k, False
    sell = None
    while d > 0 and j > 0:
        x = prices[d - 1]
        if not holding:
            if free[d][j] == free[d - 1][j]:
                d -= 1                                # rested
            else:
                sell, holding = d - 1, True           # sold on day d-1
        else:
            if hold[d][j] == hold[d - 1][j]:
                d -= 1
            else:
                out.append((d - 1, sell))             # bought on day d-1
                holding, j, d = False, j - 1, d - 1
    return free[n][k], out[::-1]

On the example, trades_k([3, 3, 5, 0, 0, 3, 1, 4], 2) returns profit 6 with trades [(0, 2), (3, 7)]: buy on day 0 at 3, sell on day 2 at 5, buy on day 3 at 0, sell on day 7 at 4. Ties mean several optimal schedules exist (buying on day 4 at 0 is just as good); because the backtrack prefers resting while it walks backwards, it picks the earliest day among equally good choices. The table costs O(nk) memory. If that is too much, store only one decision bit per state per day, or recompute with Hirschberg-style divide and conquer.

Failure modes

• Overflow in fixed-width languages. Initialising hold to INT_MIN and then adding a price wraps around in C++ or Java. Initialise to -prices[0] or use a 64-bit sentinel well below any reachable value.
• Wrong loop direction when adapting the k template to cooldown or fees, which lets one day both sell and buy. Write a brute-force checker over all schedules for arrays of length 8 and compare on random inputs before trusting a change.
• Fee applied on both edges, which charges every transaction twice. Pick one edge.
• Forgetting the shortcut, which turns a large k into an out-of-memory error.
• Empty or one-day input. The answer is 0; return early instead of indexing prices[0].
• Treating the result as a trading strategy. The DP sees the whole future. It is an upper bound for hindsight analysis, useful for scoring how much a real strategy left on the table, never a signal.

Trade-offs

The DP wins on flexibility: every new rule becomes another state or edge, and the correctness argument stays the same. The heap method is faster for large k but is hard to adapt to fees or cooldowns, so reach for it only when profiling says the O(nk) loop is the bottleneck. Compare with Kadane's maximum subarray, which is variant I in disguise: the best single trade is the maximum subarray sum of the daily price differences.

What to do next

1. Implement max_profit_k from memory, then write a brute-force checker that enumerates all schedules for arrays up to length 8 and compare on 10,000 random inputs.
2. Change one edge at a time: add the fee, then the cooldown, and rerun the checker after each change.
3. Add a minimum holding period of two days by adding states, and convince yourself the Markov property holds again.
4. Implement trades_k and verify that summing the returned trades reproduces the profit.
5. Port it to a fixed-width language and fix the sentinel overflow on purpose.
6. Read the DP fill-order walkthrough and the coin change variants to see the same choose-the-predecessor reasoning on table-shaped problems.