TL;DR
State-machine DP over (day, holding?) — O(n) time; O(n) memoized, O(1) with rolling variables.
Approach 1 — Brute-force recursion
On day i you carry one bit of state: whether you currently hold a share. You either do nothing today or take the one action the state allows (buy if free, sell if holding). Selling jumps to day i + 2, since the next day is a forced cooldown.
def maxProfit(prices: list[int]) -> int:
n = len(prices)
def dfs(i: int, holding: bool) -> int:
if i >= n:
return 0
rest = dfs(i + 1, holding) # do nothing today
if holding:
act = dfs(i + 2, False) + prices[i] # sell, then cooldown
else:
act = dfs(i + 1, True) - prices[i] # buy today
return max(rest, act)
return dfs(0, False)
Complexity: O(2^n) time, O(n) recursion depth. Each call branches in two, so the tree is exponential.
With n = 5000, 2^n is far too large to enumerate; this does not finish even for a few dozen days.
Approach 2 — Top-down memoization
The recursion only varies over (i, holding): n days times 2 holding-states gives 2n distinct subproblems. Caching them reduces the exponential tree to linear work. This is the 2-D table memo[i][holding].
from functools import lru_cache
def maxProfit(prices: list[int]) -> int:
n = len(prices)
@lru_cache(maxsize=None)
def dfs(i: int, holding: bool) -> int:
if i >= n:
return 0
rest = dfs(i + 1, holding)
if holding:
act = dfs(i + 2, False) + prices[i]
else:
act = dfs(i + 1, True) - prices[i]
return max(rest, act)
return dfs(0, False)
Complexity: O(n) time (2n states, O(1) work each), O(n) space for the cache and stack.
Approach 3 — Bottom-up three-state table
Unfold the recursion into three explicit day-states so the cooldown becomes a wiring rule rather than an index jump. For each day i:
hold[i] = best profit if you end day i holding a share.sold[i] = best profit if you sell on day i (tomorrow is cooldown).free[i] = best profit if you end day i idle and allowed to buy tomorrow.
Table meaning: dp[i][state] is the max achievable profit considering days 0..i and finishing in state.
2-D recurrence:
hold[i] = max(hold[i-1], free[i-1] - prices[i]) # keep holding, or buy from an idle day
sold[i] = hold[i-1] + prices[i] # sell what you held
free[i] = max(free[i-1], sold[i-1]) # stay idle, or land here after a sale (the cooldown)
The cooldown is enforced structurally: hold can only be entered from free, and you can only become free by first passing through sold (or by already being free).
flowchart LR
free -- buy --> hold
hold -- keep --> hold
hold -- sell --> sold
sold -- cooldown --> free
free -- idle --> free
There is no edge from sold to hold: after a sale you must land in free for one day before buying again, which is the cooldown.
def maxProfit(prices: list[int]) -> int:
n = len(prices)
hold = [0] * n
sold = [0] * n
free = [0] * n
hold[0] = -prices[0]
for i in range(1, n):
hold[i] = max(hold[i - 1], free[i - 1] - prices[i])
sold[i] = hold[i - 1] + prices[i]
free[i] = max(free[i - 1], sold[i - 1])
return max(sold[n - 1], free[n - 1])
Walkthrough on [1, 2, 3, 0, 2]:
| i | price | hold | sold | free |
|---|
| 0 | 1 | -1 | 0 | 0 |
| 1 | 2 | -1 | 1 | 0 |
| 2 | 3 | -1 | 2 | 1 |
| 3 | 0 | 1 | -1 | 2 |
| 4 | 2 | 1 | 3 | 2 |
max(sold[4], free[4]) = max(3, 2) = 3. The hold[3] = 1 cell reflects buying at price 0 on day 3 with 2 profit already banked from the earlier sale.
Complexity: O(n) time, O(n) space.
Approach 4 — Space-optimized rolling variables
The insight: every row reads only row i-1, so three scalars replace the three arrays.
def maxProfit(prices: list[int]) -> int:
if not prices:
return 0
hold = -prices[0]
sold = 0
free = 0
for price in prices[1:]:
prev_sold = sold
sold = hold + price
hold = max(hold, free - price)
free = max(free, prev_sold)
return max(sold, free)
Complexity: O(n) time, O(1) space. Note prev_sold is captured before sold is overwritten, so free sees yesterday’s sale.
Common pitfalls
- Updating the three variables in the wrong order —
sold needs yesterday’s hold, and free needs yesterday’s sold. Snapshot before overwriting.
- Off-by-one on the cooldown: selling on day
i must forbid buying on day i+1; the sold → free → hold chain guarantees a one-day gap, whereas letting hold read directly from sold would skip it.
- Initializing
hold to 0: with no share yet, “holding” on day 0 costs -prices[0], not 0.
- Returning
hold[n-1] — ending while still holding an unsold share is never optimal; answer is max(sold, free).
Pattern takeaway
When actions are gated by a small amount of history (a cooldown, a transaction cap, a “can’t repeat” rule), model each position as a handful of states and make the second table dimension the state rather than a second sequence. The recurrence becomes a state machine: write down which states can flow into which, and one linear sweep solves it.