Best Time to Buy and Sell Stock with Cooldown
Problem
prices[i] is a stock's price on day i. You may trade as
many times as you like, holding at most one share at a time, but the day right
after a sale is a mandatory cooldown on which you cannot buy. Return the
maximum total profit.prices=[1,4,2,3,0,5]Output8 (buy 1, sell 4, cool, buy 0, sell 5)prices=[3,1,4,2,6]Output5prices=[7]Output01 ≤ prices.length ≤ 5000 · 0 ≤ prices[i] ≤ 1000
Try it yourself
class Solution {
public int maxProfit(int[] prices) {
}
}
Instinct Each step you are in one of a few modes (holding, sold, cooling down) with rules for switching - keep one DP value per mode and update all of them every step.
Memory hack Name the moods, draw the moves, max the arrows - every arrow in your state diagram becomes exactly one line of code.
Open the State Machine DP guide →Approaches
Brute ForceRecursion over Every Choice
O(2n)Space O(n)At day i you either do nothing, or act: buy if empty-handed, sell
if holding. Selling jumps to day i+2, which encodes the cooldown.
Exploring every branch finds the best profit.
public int maxProfit(int[] prices) { return best(prices, 0, false); } private int best(int[] prices, int i, boolean holding) { if (i >= prices.length) return 0; int skip = best(prices, i + 1, holding); int act = holding ? prices[i] + best(prices, i + 2, false) // sell, then forced cooldown : -prices[i] + best(prices, i + 1, true); // buy return Math.max(skip, act); }
Captures the rules exactly, but the same (day, holding) pair is re-solved exponentially often.
BetterMemoised DP on (day, holding)
O(n)Space O(n)There are only 2n distinct subproblems, so cache each result in
memo[i][holding]. Every state is computed once in O(1).
private Integer[][] memo; public int maxProfit(int[] prices) { memo = new Integer[prices.length][2]; return best(prices, 0, 0); } private int best(int[] prices, int i, int holding) { if (i >= prices.length) return 0; if (memo[i][holding] != null) return memo[i][holding]; int skip = best(prices, i + 1, holding); int act = holding == 1 ? prices[i] + best(prices, i + 2, 0) : -prices[i] + best(prices, i + 1, 1); return memo[i][holding] = Math.max(skip, act); }
Linear time; the table (and recursion stack) costs O(n) memory.
OptimalThree-State Machine, O(1) Space
O(n)Space O(1)Track hold, sold, rest = best profit
ending today in each state. Transitions: sold = hold + p;
hold = max(hold, rest - p) (buy only from rest, never right after a
sale); rest = max(rest, yesterday's sold).
public int maxProfit(int[] prices) { int hold = -prices[0]; // bought on day 0 int sold = 0; // sold today (tomorrow is cooldown) int rest = 0; // no share, free to buy for (int i = 1; i < prices.length; i++) { int prevSold = sold; sold = hold + prices[i]; hold = Math.max(hold, rest - prices[i]); rest = Math.max(rest, prevSold); } return Math.max(sold, rest); }
Dry runprices=[1,4,2,3,0,5]
- i=01i42305h=-1 s=0 r=0
- i=114i2305sell: h=-1 s=3 r=0
- i=2142i305cool: h=-1 s=1 r=3
- i=31423i05h=0 s=2 r=3
- i=414230i5buy: h=3 s=0 r=3
- i=5142305isell: s=8 ✔
Same recurrence, rolled into three variables — the cleanest answer.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Recursion over Every Choice | O(2n) | O(n) |
| Better | Memoised DP on (day, holding) | O(n) | O(n) |
| Optimal | Three-State Machine, O(1) Space | O(n) | O(1) |
- Buying from
soldinstead ofrest— that skips the cooldown. - Updating
restwith today's newsoldinstead of yesterday's (saveprevSold). - Starting
holdat 0 — it would pretend you own a free share.
- Name the states aloud and draw the transitions before writing any code.
- Show the recursion first, point out the repeated (day, holding) pairs, then memoise.
- Finish by rolling the table into variables and mention the 714 (fee) variant.