#309
Best Time to Buy and Sell Stock with Cooldown
Medium State machine DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Trade as many times as you like, holding at most one share, but after selling you must wait one day before buying again. Maximise profit.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: unlimited trades, but a day of rest after selling.
Why this works: three states per day: holding, just sold, resting. You may only buy from resting.
Example: [1, 2, 3, 0, 2]
buy 1, sell 2, cooldown, buy 0, sell 2 → 3✦Hints open one at a time
Track three states per day: holding a share, just sold (cooldown next), and resting (free to buy).
hold = max(hold, rest − price); sold = hold + price; rest = max(rest, sold).
↗Approach
Update the three states each day using yesterday's values. The answer is max(sold, rest).
</>Solution (Java)
class Solution {
public int maxProfit(int[] prices) {
int hold = Integer.MIN_VALUE / 2, sold = 0, rest = 0;
for (int p : prices) {
int prevSold = sold;
sold = hold + p; // sell today
hold = Math.max(hold, rest - p); // buy only from rest (cooldown respected)
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
}
}!Common mistake
Buying from yesterday's "sold" state — that skips the cooldown.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon