Best Time to Buy and Sell Stock with Cooldown
MediumDynamic Programming
You are given prices, where prices[i] is the price of a stock on day i. You may make as many trades as you like (buy one share, later sell it), subject to these rules:
- You can hold at most one share at a time, so you must sell before buying again.
- After you sell on day
i, you cannot buy on dayi + 1(a one-day cooldown). Buying on dayi + 2or later is fine. - Selling and buying on the same day is not allowed.
Return the maximum total profit you can achieve. If no trade is profitable, return 0.
Example 1
- Input:
- prices = [2,1,4,5,2,9,7]
- Output:
- 10
- Explanation
- Buy at 1 and sell at 4 (+3), rest on the next day (price 5) because of the cooldown, then buy at 2 and sell at 9 (+7), for 10 total. Holding from 1 straight to 9 would make only 8.
Example 2
- Input:
- prices = [0,1,0,1]
- Output:
- 1
- Explanation
- Buying at 0 and selling at 1 twice would need a buy the day right after a sale, which the cooldown forbids. One trade for a profit of 1 is the best possible.
Example 3
- Input:
- prices = [5,4,3]
- Output:
- 0
- Explanation
- Prices only fall, so any trade loses money. Not trading at all gives 0.
Constraints
1 <= prices.length <= 50000 <= prices[i] <= 1000