TL;DR
State-machine DP over (day, holding?) — O(n) time; O(n) memoized, O(1) with rolling variables.
Approach 1 — Brute-force recursion
Intuition: stand on day i with one bit of state — are you currently holding a share? From there you either do nothing today, or take the one action your state allows (buy if free, sell if holding). Selling jumps to day i + 2 because the next day is a forced cooldown.
class Solution:
def maxProfit(self, 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.
Why the constraints kill it: with n = 5000, 2^n is astronomically large — it won’t finish for even 40 days.
Approach 2 — Top-down memoization
The insight: the recursion only ever varies over (i, holding) — n days times 2 holding-states = 2n distinct subproblems. Cache them and the exponential tree collapses to linear. This is the 2-D table memo[i][holding].
from functools import lru_cache
class Solution:
def maxProfit(self, 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
The insight: 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).
class Solution:
def maxProfit(self, 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 captures “buy the 0 while sitting on 2 profit already banked.”
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.
class Solution:
def maxProfit(self, 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.