Best Time to Buy and Sell Stock with Cooldown
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ prices.length ≤ 12 - ◆
0 ≤ prices[i] ≤ 1000
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Without Memoization
BruteExtend the plain unlimited-trades recursion with a third piece of state: whether today is a forced cooldown day. A cooldown day has exactly one legal move — sit out and move on — so it collapses back to the two-way "do nothing or act" branch on the very next day. The moment a sale happens, the following day is marked as a cooldown before recursing. As with the plain version, the same (day, holding, cooldown) situation gets rediscovered from many different pasts, so trying every branch without remembering past answers costs roughly double the work per extra day.
O(2ⁿ)O(n)1class Solution {
2 private int[] prices;
3
4 public int maxProfit(int[] prices) {
5 this.prices = prices;
6 return solve(0, false, false);
7 }
8
9 private int solve(int day, boolean holding, boolean cooldown) {
10 if (day >= prices.length) return 0;
11 if (cooldown) return solve(day + 1, holding, false);
12 int doNothing = solve(day + 1, holding, false);
13 int act;
14 if (holding) {
15 act = prices[day] + solve(day + 1, false, true);
16 } else {
17 act = -prices[day] + solve(day + 1, true, false);
18 }
19 return Math.max(doNothing, act);
20 }
21}Optimal — Three-State Bottom-Up DP
OptimalInstead of exploring both branches at every day, track the best profit reachable in exactly three situations after each day: `hold` (currently own a share), `sold` (just sold today, so tomorrow is forced to be a cooldown), and `rest` (own nothing and free to buy). Each day, `hold` either keeps yesterday's held position or buys fresh using yesterday's `rest` balance; `sold` always comes from yesterday's `hold` plus today's price; and `rest` carries forward the better of yesterday's `rest` or `sold`, since a completed sale always clears its cooldown by the day after next. The answer is whichever of `sold` or `rest` is larger once every day is processed — never `hold`, since ending the whole sequence still holding a share is by definition worse than having sold it at some point.
O(n)O(1)1class Solution {
2 public int maxProfit(int[] prices) {
3 int n = prices.length;
4 if (n == 0) return 0;
5 int hold = -prices[0], sold = 0, rest = 0;
6 for (int i = 1; i < n; i++) {
7 int prevHold = hold, prevSold = sold, prevRest = rest;
8 hold = Math.max(prevHold, prevRest - prices[i]);
9 sold = prevHold + prices[i];
10 rest = Math.max(prevRest, prevSold);
11 }
12 return Math.max(sold, rest);
13 }
14}