Best Time to Buy and Sell Stock with Cooldown
Maximise stock profit when every sale is followed by a one-day cooldown, with three DP states per day: hold, sold and rest.
Problem Understanding
Best Time to Buy and Sell Stock with Cooldown: prices[i] is the price on day i. You may complete as many trades as you like, holding at most one share at a time, but after you sell you cannot buy on the next day. Return the maximum profit.
Example: prices = [1, 2, 3, 0, 2] returns 3: buy, sell, cooldown, buy, sell.
The Intuition: Three States, One Day at a Time
At the end of any day you are in exactly one situation, and the rules only care about that:
- hold: you own a share. You got here by holding yesterday, or by buying today, which is only allowed from rest.
- sold: you sold today. You got here only from hold, earning today's price.
- rest: you own nothing and are free. You got here by resting yesterday, or because yesterday you sold and today is the cooldown.
Keep the best profit for each state and update all three from yesterday's values. That is a small state machine, a classic shape of dynamic programming on sequences, and it needs only three variables. Without the cooldown, Stock II is solved greedily; with one trade only, Stock I tracks the lowest price so far.
Interactive Walkthrough
Each column is a day; the rows hold the best profit for hold, sold and rest. The day being computed is solid and the column it reads is tinted. At the end the best path turns green with its buys and sells. Try Zigzag to see the cooldown cost a trade.
Dry Run Table
Input: prices = [1, 2, 3, 0, 2]
| Day | Price | hold | sold | rest |
|---|---|---|---|---|
| 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 |
- Day 3:
hold = max(-1, rest 1 - 0) = 1: buy at 0 after the day-2 cooldown. - Day 4:
sold = 1 + 2 = 3.
Answer: max(sold 3, rest 2) = 3: buy 1, sell 2, cooldown, buy 0, sell 2.
The Solution Template
Three rolling variables. prevSold keeps yesterday's sold, because rest needs it after sold is overwritten.
Best Time to Buy and Sell Stock with Cooldown Code
1var maxProfit = function(prices) {2 let hold = -prices[0], sold = 0, rest = 0;3 for (let i = 1; i < prices.length; i++) {4 const prevSold = sold;5 sold = hold + prices[i];6 hold = Math.max(hold, rest - prices[i]);7 rest = Math.max(rest, prevSold);8 }9 return Math.max(sold, rest);10};
Edge Cases & Common Mistakes
- One day: no sale is possible; the answer is 0.
- Falling prices: never buy;
reststays 0. - Updating in the wrong order:
restneeds yesterday'ssoldandholdneeds yesterday'srest; saveprevSoldor use temporaries. - Buying from sold: that is buying the day after a sale, which the cooldown forbids. Buy only from
rest. - Returning hold: ending with a share you never sold can never beat
max(sold, rest).
Summary
Track three states per day: hold, sold and rest. sold = hold + price, hold = max(hold, rest - price), rest = max(rest, previous sold). Return max(sold, rest). O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet