Best Time to Buy and Sell Stock with Cooldown
You are given an array prices where prices[i] is the stock price on day i. You may complete as many transactions as you like, but you may hold at most one share at a time — you must sell before buying again. There is one extra rule: after you sell, you must skip the following day entirely and cannot buy on it. Return the maximum profit achievable. Doing nothing is allowed, so the answer is never negative.
- 1 ≤ prices.length ≤ 5000
- 0 ≤ prices[i] ≤ 1000
- You may hold at most one share at any moment
- After a sale on day i, the earliest possible buy is day i + 2
prices = [1, 2, 3, 0, 2]3prices = [1]0prices = [1, 2, 3, 4, 5]4prices = [2, 1, 4]3prices = [6, 1, 3, 2, 4, 7]6With unlimited transactions and no cooldown, this problem is famously easy: add up every upward move, because any rise from day i to day i+1 can be captured by buying and selling on consecutive days, and a long climb is the sum of its daily steps. On [1, 2, 3] you would collect (2−1) + (3−2) = 2, the same as buying at 1 and selling at 3.
The cooldown destroys that argument. Chopping one long hold into many small trades now costs you a forced rest day after each sale, and those lost days can be more valuable than the flexibility. So the two are no longer equivalent, and we have to decide, day by day, whether to trade — which is exactly what these tables are for.
Also worth stating precisely: the cooldown applies after selling only. Buying carries no penalty. And the rest day is a single day, so a sale on day i permits a purchase from day i+2 onward.
Say I am standing on day i. What do I actually need to know to decide what to do?
So besides the day, the one thing that decides my options is: am I holding a share right now? That single yes/no is the rest of the state.
f(i, holding) is the most profit I can still make from day i to the end, where holding says whether I already own a share as day i begins.Two cases, each with two options.
If I am holding a share, I can:
- sell today → collect prices[i], and the cooldown kicks in, so the next day I may act is i + 2: prices[i] + f(i+2, not holding).
- keep holding → do nothing, still holding tomorrow: f(i+1, holding).
If I am not holding, I can:
- buy today → pay prices[i] and now I hold a share: -prices[i] + f(i+1, holding).
- do nothing → still empty-handed tomorrow: f(i+1, not holding).
Take the better option in each case:
f(i, holding) = max( prices[i] + f(i+2, not holding), f(i+1, holding) )f(i, not holding) = max( −prices[i] + f(i+1, holding), f(i+1, not holding) )
The whole cooldown rule lives in one spot: the i+2 after a sale. Buying and waiting just step to i+1.
Buying subtracts the price and selling adds it, so the running total is real cash — no need to remember what you paid.
Base case: once i runs past the last day (i >= n), nothing is left to earn, so f = 0. A share still held at the end earns nothing, which correctly rules out buying and never selling.
The answer is f(0, not holding) — day 0, nothing owned yet.
Memoised, straight from the story. holding is a boolean:
def max_profit(prices):
n = len(prices)
memo = {}
def f(i, holding):
if i >= n: return 0
if (i, holding) in memo: return memo[(i, holding)]
if holding:
best = max(prices[i] + f(i + 2, False), # sell -> cooldown -> skip to i+2
f(i + 1, True)) # keep holding
else:
best = max(-prices[i] + f(i + 1, True), # buy today
f(i + 1, False)) # do nothing
memo[(i, holding)] = best
return best
return f(0, False)There are n days × 2 holding-values = 2n states, constant work each, so O(N) time.
Now the table. Let dp[i][h] hold what f(i, h) returned. Each recurrence line becomes an array assignment. The reads reach forward — to i+1 and i+2 — so fill from the last day backwards. Give the table two extra rows so the i+2 read is always valid and lands on the base value 0:
def max_profit(prices):
n = len(prices)
dp = [[0, 0] for _ in range(n + 2)] # dp[i][0] = not holding, dp[i][1] = holding
for i in range(n - 1, -1, -1):
dp[i][1] = max(prices[i] + dp[i + 2][0], dp[i + 1][1]) # holding: sell or keep
dp[i][0] = max(-prices[i] + dp[i + 1][1], dp[i + 1][0]) # empty: buy or wait
return dp[0][0]And since each day reads only one and two days ahead, we can keep just those two rows instead of the whole table:
def max_profit(prices):
n = len(prices)
ahead1 = [0, 0] # dp[i+1]
ahead2 = [0, 0] # dp[i+2]
for i in range(n - 1, -1, -1):
cur = [0, 0]
cur[1] = max(prices[i] + ahead2[0], ahead1[1])
cur[0] = max(-prices[i] + ahead1[1], ahead1[0])
ahead2, ahead1 = ahead1, cur
return ahead1[0]O(1) space.
[not holding, holding]. Days at or past the end are [0, 0].[0, 2][2, 2][2, 3][2, 4][3, 4]Answer dp[0][0] = 3: buy at 1, sell at 2 (profit 1), cooldown, buy at 0, sell at 2 (profit 2).
Notice what the table rejected. Buying at 1 and selling at 3 on day 2 earns 2, but the forced rest on day 3 misses the price of 0, and you cannot do better after — total 2. The cooldown genuinely changed the best plan.
The move that cracked this is worth keeping: when the day alone is not enough, ask what else decides your options, and add exactly that to the state. Here it was one yes/no — am I holding a share? Two situations on the same day with different holdings face different futures, so the holding must be in the state.
And notice how the cooldown was handled: not with a new "resting" state, but as a jump in the index — a sale sends you to i+2 instead of i+1. A "you must wait k steps after doing X" rule almost always becomes a longer jump like this.
The rest of the stock family follows the same recipe. A transaction fee subtracts a constant on the sell step. "At most k transactions" adds a counter, making the state (day, holding, transactions left). In every case the state grows by exactly what the new rule cares about, and nothing else.