Best Time to Buy and Sell Stock with Cooldown
MediumThe problem
prices[i] is a stock price on day i. You may buy and sell as many times as you like, but you can hold only one share at a time and must sell before buying again. After you sell, you cannot buy on the very next day (a one-day cooldown). Return the biggest total profit.
- Example 1Input: prices = [1, 2, 3, 0, 2]Output: 3
Buy at 1, sell at 2, rest a day, buy at 0, sell at 2: 1 + 2 = 3.
- Example 2Input: prices = [1]Output: 0
There is no way to make a profit with one day.
- 1 ≤ len(prices) ≤ 5,000
- 0 ≤ prices[i] ≤ 1,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
On each day you are in one of a few states: holding, just sold (cooling), or resting.
The idea
State machine: hold = max(hold, rest − price); sold = hold + price; rest = max(rest, previous sold). Iterate over the days.
Target: O(n) time, O(1) space
Go function shape
func maxProfit(prices []int) intReference solution
Tested with go test. Try it yourself first, then compare.
// MaxProfitCooldown: unlimited trades, but you must rest one day after selling.
// Three states per day: holding a stock, just sold (cooling down), or resting with nothing.
func MaxProfitCooldown(prices []int) int {
hold, sold, rest := -1<<31, 0, 0
for _, p := range prices {
prevSold := sold
sold = hold + p
hold = max(hold, rest-p)
rest = max(rest, prevSold)
}
return max(sold, rest)
}