DSA Tracker

Visualize

Best Time to Buy and Sell Stock with Cooldown

Three running states per day: hold, sold-today, resting

time O(n)space O(n)

Every day you are in exactly one of three states: holding a share, having just sold one (which forces tomorrow to be a rest day), or resting with nothing held. Each state's best profit only depends on yesterday's states, so track three running values — hold, sold, rest — and update all three every day from yesterday's numbers. The cooldown rule shows up as one missing edge: today's hold can come from yesterday's rest but never from yesterday's sold, since selling and immediately buying the next day is exactly what cooldown forbids.

Details

Animated on: prices = [1, 2, 3, 0, 2] — after selling you must cooldown for one day before buying again. Find the max profit.

Problem:Best Time to Buy and Sell Stock with CooldownMedium

Three running states per day: hold, sold-today, resting

step 1 / 14

prices = [1, 2, 3, 0, 2]

Day 0 base case: hold[0] = -1 (buying today is the only way to hold), sold[0] = 0 and rest[0] = 0 (no trade has happened yet, so no profit either way).

Pseudocode
1FUNCTION maxProfit(prices):
2  n <- LENGTH(prices)
3  hold[0] <- -prices[0]
4  sold[0] <- 0
5  rest[0] <- 0
6  FOR i FROM 1 TO n-1:
7    hold[i] <- MAX(hold[i-1], rest[i-1] - prices[i])
8    sold[i] <- hold[i-1] + prices[i]
9    rest[i] <- MAX(rest[i-1], sold[i-1])
10  RETURN MAX(sold[n-1], rest[n-1])

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. Day 0 base case: hold[0] = -1 (buying today is the only way to hold), sold[0] = 0 and rest[0] = 0 (no trade has happened yet, so no profit either way).
  2. hold[1] = MAX(hold[0] = -1, rest[0] - 2 = -2) = -1 — either keep yesterday's holding position, or buy today, which is only legal because rest[0] (not cooldown) can afford it.
  3. sold[1] = hold[0] + 2 = -1 + 2 = 1 — selling today is only reachable from yesterday's holding state, since you need a share in hand to sell.
  4. rest[1] = MAX(rest[0] = 0, sold[0] = 0) = 0 — today's rest is either a continued rest, or the mandatory cooldown day forced by selling yesterday.
  5. hold[2] = MAX(hold[1] = -1, rest[1] - 3 = -3) = -1 — either keep yesterday's holding position, or buy today, which is only legal because rest[1] (not cooldown) can afford it.
  6. sold[2] = hold[1] + 3 = -1 + 3 = 2 — selling today is only reachable from yesterday's holding state, since you need a share in hand to sell.
  7. rest[2] = MAX(rest[1] = 0, sold[1] = 1) = 1 — today's rest is either a continued rest, or the mandatory cooldown day forced by selling yesterday.
  8. hold[3] = MAX(hold[2] = -1, rest[2] - 0 = 1) = 1 — either keep yesterday's holding position, or buy today, which is only legal because rest[2] (not cooldown) can afford it.
  9. sold[3] = hold[2] + 0 = -1 + 0 = -1 — selling today is only reachable from yesterday's holding state, since you need a share in hand to sell.
  10. rest[3] = MAX(rest[2] = 1, sold[2] = 2) = 2 — today's rest is either a continued rest, or the mandatory cooldown day forced by selling yesterday.
  11. hold[4] = MAX(hold[3] = 1, rest[3] - 2 = 0) = 1 — either keep yesterday's holding position, or buy today, which is only legal because rest[3] (not cooldown) can afford it.
  12. sold[4] = hold[3] + 2 = 1 + 2 = 3 — selling today is only reachable from yesterday's holding state, since you need a share in hand to sell.
  13. rest[4] = MAX(rest[3] = 2, sold[3] = -1) = 2 — today's rest is either a continued rest, or the mandatory cooldown day forced by selling yesterday.
  14. You must end the last day NOT holding a stock, so the answer is MAX(sold[4] = 3, rest[4] = 2) = 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Best Time to Buy and Sell Stock with Cooldown in the editorAll Dynamic Programming problemsBack to roadmap