Best Time to Buy and Sell Stock with Cooldown
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
You are given prices, where prices[i] is the price of a stock on day i. You may complete as many transactions as you like, under two rules:
- You hold at most one share at a time, so you must sell before you buy again.
- After you sell, you must wait one full day (a cooldown) before buying again.
Return the maximum profit you can achieve. Doing nothing earns 0.
Examples
Input: prices = [2,6,1,1,5] Output: 8
Buy on day 0, sell on day 1 (+4), cool down on day 2, buy on day 3, sell on day 4 (+4).
Input: prices = [3,1,4,2,6] Output: 5
Buy at 1 and hold to 6. Selling at 4 first would force a cooldown on the day the price is 2.
Input: prices = [7] Output: 0
With a single day nothing can be sold.
Constraints
- 1 <= len(prices) <= 5000
- 0 <= prices[i] <= 1000
Approaches
- For each sell day, try every buy day — time O(n²), space O(n)
Follow-up
What if each sale also paid a fixed fee? Subtract the fee in the "sold" transition; the three states stay the same. And for a cooldown of k days, "rest" needs to remember sales from k + 1 days back instead of one.
Related problems
Start free on Cariara · Coding problems · System design studio
