The problem
prices[i] is a stock’s price on day i. You may buy and sell as many times as you like, but hold at most one share at a time, and after selling you must wait a day (a cooldown) before buying again.
Return the most profit you can make.
Examples
- Input
prices = [1, 2, 3, 0, 2]
- Output
3
- Input
prices = [1]
- Output
0
Constraints
- 1 ≤ prices.length ≤ 5000
- 0 ≤ prices[i] ≤ 1000
The idea
At the end of each day you are in one of three states: holding a share, having just sold one today, or resting with none (free to buy tomorrow). Track the best profit for each.
Tomorrow: hold = max(keep holding, buy from rest — rest − price); sold = hold + price; rest = max(keep resting, come off yesterday’s sale). Buying only from rest, never straight from sold, is the cooldown. The answer is the better of sold and rest at the end.
- Time
- O(n)
- Space
- O(1) — three numbers
Solution · every language run against every case
class Solution: def maxProfit(self, prices: List[int]) -> int: # The best profit at the end of each day, in each of three states: # hold: owning a share; sold: sold one today (so tomorrow must rest); rest: free to buy. hold, sold, rest = float("-inf"), 0, 0 for p in prices: hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold) return max(sold, rest)