Trades With Cooldown
Medium1-D Dynamic Programming
Problem
prices[i] is a share's price on day i. You may complete as many buy-then-sell trades as you like, holding at most one share at a time.
After you sell, the exchange makes you sit out the next day: you cannot buy on the day right after a sale. Return the maximum total profit.
Example 1
- Input:
- prices = [1, 2, 3, 0, 2]
- Output:
- 3
Buy at 1, sell at 2, cool down on day 2, buy at 0, sell at 2.
Example 2
- Input:
- prices = [1]
- Output:
- 0
Constraints
- 1 ≤ prices.length ≤ 5000
- 0 ≤ prices[i] ≤ 1000
Hint
Show the first hint
With two states (holding / not holding) you cannot tell whether buying today is allowed. What extra fact do you need?
Walkthrough
How to approach it
01Clarify before coding
- Does the cooldown apply after buying too? No, only the day after a sale.
- Can I sell and buy on the same day? No: buying the day after a sale is already forbidden, so the same day is too.
- Must I end without a share? Holding at the end never helps.
02Brute force
Recurse over days with flags (holding, in cooldown), trying buy, sell or wait. Memoising on (day, state) turns it into the DP below.
Cost: Without memo: O(3ⁿ)-ish branching. With memo: O(n) states × 3, O(n) space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.