#309 Best Time to Buy and Sell Stock with Cooldown
the problem
In plain words
prices[i] is the price of one stock on day i. You may trade as often as you like, holding at most one share at a time. After every sale you must sit out the next day before you buy again. Return the largest total profit you can make.
in prices = [1,2,3,0,2]
out 3
Buy on day 0, sell on day 1, cool down on day 2, buy on day 3, sell on day 4: 1 + 2 = 3.
in prices = [1]
out 0
- 1 ≤ prices.length ≤ 5000
- 0 ≤ prices[i] ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternState-machine DP
At the end of each day you are in one of three modes: HOLD (you own a share), SOLD (you sold today, so tomorrow is blocked) or REST (you own nothing and may buy). Keep the best profit for each mode; every legal move between modes is one line of Math.max.
solutions
From brute force to optimal
best(day, holding): rest today, or act — buy if you hold nothing, or sell and jump two days ahead.
- Past the last day → 0.
- rest = best(day + 1, holding).
- Holding: sell = price + best(day + 2, false). Not holding: buy = −price + best(day + 1, true).
- Return the larger.
Two choices every day and nothing is remembered: the call tree roughly doubles per day.
The recursion goes one level deeper per day.
class Solution { public int maxProfit(int[] prices) { return best(prices, 0, false); } /** Best profit from day i to the end, given whether we hold a share right now. */ private int best(int[] prices, int i, boolean holding) { if (i >= prices.length) return 0; int rest = best(prices, i + 1, holding); // do nothing today int act = holding ? prices[i] + best(prices, i + 2, false) // sell today; tomorrow is the cooldown : -prices[i] + best(prices, i + 1, true); // buy today return Math.max(rest, act); }}Only 2n different (day, holding) pairs exist — cache each one.
- int[n][2] memo filled with −1 (real answers are never negative).
- Check, compute, store.
2n states, O(1) work each.
The memo plus a recursion up to n deep.
class Solution { public int maxProfit(int[] prices) { int[][] memo = new int[prices.length][2]; // memo[i][holding]; -1 = unknown (answers are never negative) for (int[] row : memo) Arrays.fill(row, -1); return best(prices, 0, 0, memo); } private int best(int[] prices, int i, int holding, int[][] memo) { if (i >= prices.length) return 0; if (memo[i][holding] != -1) return memo[i][holding]; int rest = best(prices, i + 1, holding, memo); int act = holding == 1 ? prices[i] + best(prices, i + 2, 0, memo) : -prices[i] + best(prices, i + 1, 1, memo); return memo[i][holding] = Math.max(rest, act); }}dp[d][HOLD/SOLD/REST] = best profit after the first d days, ending in that mode.
- dp[0] = (−∞, −∞, 0).
- HOLD = max(HOLD, REST − p); SOLD = HOLD + p; REST = max(REST, SOLD), all from row d − 1.
- Answer max(SOLD, REST) in the last row.
n rows × 3 cells, O(1) each.
The (n + 1) × 3 table.
class Solution { public int maxProfit(int[] prices) { int n = prices.length; final int HOLD = 0, SOLD = 1, REST = 2; int[][] dp = new int[n + 1][3]; // dp[d][state]: best profit after the first d days, ending in that state dp[0][HOLD] = Integer.MIN_VALUE / 2; // can't hold a share before day 0 (half of MIN so "+ price" can't overflow) dp[0][SOLD] = Integer.MIN_VALUE / 2; // can't have sold one either dp[0][REST] = 0; for (int d = 1; d <= n; d++) { int p = prices[d - 1]; dp[d][HOLD] = Math.max(dp[d - 1][HOLD], dp[d - 1][REST] - p); // keep holding, or buy (only from REST) dp[d][SOLD] = dp[d - 1][HOLD] + p; // sell the share we held dp[d][REST] = Math.max(dp[d - 1][REST], dp[d - 1][SOLD]); // stay out, or cool down after a sale } return Math.max(dp[n][SOLD], dp[n][REST]); }}Row d only reads row d − 1, so keep three ints and save yesterday's before overwriting.
- hold = sold = −∞, rest = 0.
- Each day: save the three; hold = max(pH, pR − p); sold = pH + p; rest = max(pR, pS).
- Return max(sold, rest).
One pass, a few max() calls per day.
Six ints, whatever n is.
class Solution { public int maxProfit(int[] prices) { int hold = Integer.MIN_VALUE / 2; // best profit while holding a share: impossible before day 0 int sold = Integer.MIN_VALUE / 2; // best profit if we sold today int rest = 0; // best profit holding nothing, free to buy for (int p : prices) { int prevHold = hold, prevSold = sold, prevRest = rest; // yesterday's three numbers hold = Math.max(prevHold, prevRest - p); // keep holding, or buy (never right after a sale) sold = prevHold + p; // sell the share we were holding rest = Math.max(prevRest, prevSold); // stay out, or yesterday's sale cools down } return Math.max(sold, rest); // ending while holding a share is never best }}Walk the machine day by day
in the room
How to say it in the interview
talk track
- Draw three circles: HOLD, SOLD, REST. Arrows: REST → HOLD (buy), HOLD → SOLD (sell), SOLD → REST (cool down); HOLD and REST may also stay.
- "Each arrow is one max(). I save yesterday's three numbers first, so today's updates never read each other."
- "The answer is max(SOLD, REST) — ending while still holding a share is never better." Then O(n) time, O(1) memory.
traps
- Buying from SOLD skips the cooldown. A buy must come from REST.
- Computing sold from today's new hold: that sells a share bought the same day. Use the saved prevHold.
- Starting hold at 0 pretends you own a free share; start it at −∞ (or −prices[0]).
what they ask next
Follow-ups
A cooldown of c days instead of one?
In the table version, buy from REST of day d − c instead of d − 1 (keep the last c + 1 rows); the machine itself is unchanged.
A transaction fee as well?
Put the fee on the sell arrow: sold = prevHold + p − fee. Nothing else changes — that's LC 714 plus a cooldown.
before you submit
Edge cases to test
- One day → 0: you can't buy and sell on different days.
- Prices only fall, or stay flat → 0.
- [1,3,1,3,1,3] → 4, not 6: the cooldown blocks buying the day after each sale.
practise next
Similar problems
- #714Best Time to Buy and Sell Stock with Transaction FeeMediumin DP Patterns
- #122Best Time to Buy and Sell Stock IIMediumin Arrays & Strings
- #198House RobberMediumin Dynamic Programming