Difficulty: Medium2-D Dynamic Programming

Best Time to Buy and Sell Stock with Cooldown

Problem in Plain English

Each day lists a stock price, you may hold at most one share, and selling forces you to skip buying on the next day. Choose any number of buy and sell days to maximise total profit under that cooldown rule.

Problem Statement

You are given an array prices where prices[i] is the price of a stock on day i. You may complete as many transactions as you like, but you must sell before you can buy again, and after selling you enter a one-day cooldown during which buying is forbidden.

Holding at most one share at a time, pick buy and sell days that respect the cooldown and maximise total profit. Doing nothing is always allowed, so the answer is never negative.

Return that maximum achievable profit.

Constraints

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

Examples

Example 1

Input: prices = [1, 2, 3, 0, 2]
Output: 3

Buy day 0, sell day 1 (profit 1), cooldown day 2, buy day 3, sell day 4 (profit 2); total 3.

Example 2

Input: prices = [1]
Output: 0

A single day allows no completed transaction.

Example 3

Input: prices = [1, 2, 0, 2]
Output: 2

Buying at 1 and selling at 2 earns 1 but blocks buying at 0 on the next day. Skip that trade, buy at 0 on day 2 and sell at 2 on day 3 to earn 2. Adding every upward price difference would incorrectly report 3.

Example 4

Input: prices = [5, 4, 3, 1]
Output: 0

Every later selling price is below its buying price, so all completed trades lose money. Taking no trades earns 0 and is optimal.

Intuition

A sale changes tomorrow's options: being empty-handed after selling is different from being empty-handed after resting. On [1, 2, 3, 0, 2], selling at 3 blocks the attractive buy at 0, while selling earlier at 2 leaves that buy available and earns 3 overall. Keep track of holding, cooling down, and being free to buy; profit alone does not say which actions remain legal.

Approaches

Recursive Day Choice

Solution Details

Reveal Recursive Day Choice: intuition, complexity, and code

Intuition

Search every legal daily action, returning the best additional cash flow from the current day onward. The state records whether a share is held and whether buying is blocked today. Buying subtracts its price, selling adds its price, and cooling down forces a rest. Repeated states are recomputed, which makes this a useful small-input baseline.

Step-by-Step Logic

Define dfs(day, holding, cooling) as the maximum additional cash flow from that state, with no share left at the end. Return 0 past the last day when empty-handed and a very negative value when holding.
Always try resting: advance one day with the same holding status and clear the cooldown. When holding, also try selling and mark tomorrow as cooling; when free, also try buying. Never buy on a cooldown day.
Add the sale price or subtract the purchase price before comparing trade and rest. In Example 1, dfs(1, holding, false) returns 4, so buying on day 0 gives -1 + 4 = 3; resting on day 0 gives 2.
Take the maximum at every return. The winning Example 1 branch buys at 1, sells at 2, rests through price 3, buys at 0, and sells at 2; its cash flow is -1 + 2 + 0 + 0 + 2 = 3.
Return the initial free-state value. The table merges repeated calls by state only for readability; the implementation has no cache.

Why It Works

At each state, rest and the permitted trade partition all possible schedules by their next action. A holding state can sell or keep its share; a free state can buy or rest; a cooldown state must rest. Passing cooling = true after a sale and clearing it after one rest enforces exactly one forbidden buying day. At the end, empty-handed states return 0 and holding states return an impossible negative sentinel, so only completed transactions can win. Inductively, adding today's cash flow to the best valid suffix and taking the maximum gives the best schedule from each state, including the initial free state.

Dry Run

Recursive Day Choice: variable states at each step
day / price	state	rest suffix	trade cash + suffix	returned best
5 / end	empty-handed, free or cooling	—	—	0
5 / end	holding	—	—	-1000000000 (invalid)
4 / 2	free	0	-2 - 1000000000 = -1000000002	0
4 / 2	cooling	0	forbidden	0
4 / 2	holding	-1000000000	2 + 0 = 2	2
3 / 0	free	0	0 + 2 = 2	2
3 / 0	cooling	0	forbidden	0
3 / 0	holding	2	0 + 0 = 0	2
2 / 3	free	2	-3 + 2 = -1	2
2 / 3	cooling	2	forbidden	2
2 / 3	holding	2	3 + 0 = 3	3
1 / 2	free	2	-2 + 3 = 1	2
1 / 2	holding	3	2 + 2 = 4	4
0 / 1	free	2	-1 + 4 = 3	return 3

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be the number of days. Each call advances one day and creates at most two children, giving an O(2^n) upper bound, not an exact doubling: cooldown nodes have only one child. The recursion depth and live stack storage are O(n), with no array copies or cache. Exponential work makes n = 5000 infeasible. The sentinel -1000000000 is safely below any feasible cash flow under the price and length bounds; Java int and JavaScript numbers safely hold all calculations.

Code

Solution.java

1class Solution {2    public int maxProfit(int[] prices) {3        return dfs(prices, 0, false, false);4    }5
6    private int dfs(int[] prices, int day, boolean holding, boolean cooling) {7        // An unfinished purchase cannot count as a completed transaction.8        if (day >= prices.length) return holding ? -1000000000 : 0;9        int rest = dfs(prices, day + 1, holding, false);10        if (holding) {11            return Math.max(rest, prices[day] + dfs(prices, day + 1, false, true));12        }13        // Rest clears the one-day restriction; buying today is forbidden.14        if (cooling) return rest;15        return Math.max(rest, -prices[day] + dfs(prices, day + 1, true, false));16    }17}

Hints

Hint 1

Name what can be true overnight: holding a share, having just sold, or sitting out free with no restriction.

Hint 2

Write one update per state: holding keeps or buys from rest, selling must come from holding, resting keeps or follows a sale.

Hint 3

Each day only reads yesterday, so yesterday’s three numbers are the entire memory you need.

Edge Cases

A single day such as prices = [1], where no sale is possible and the answer is 0.
Strictly falling prices such as prices = [5, 4, 3, 1], where every trade loses and sitting out wins with 0.
A sale on the last day, which is allowed since the cooldown would fall outside the array.
A zero-price purchase may make hold positive after earlier profits; hold is net cash flow, not the stock's price. Equal prices cannot improve profit.

Common Mistakes and Interview Tips

Buying the day after a sale, which violates the cooldown; buys must come from the resting state only.
Sell-then-rebuy greedy peak picking, which ignores that the forced rest can erase the gain of a quick second trade.
Updating the three states in place without snapshots, so sold reads an already-updated hold from the same day.
Returning hold as a final candidate counts an unfinished position. In an interview, define the end-of-day states and their initial reachable values before writing transitions.

Key Takeaway

When today’s choices restrict tomorrow’s, model each day as a small set of states and roll their best values forward with fixed transition rules.