You are given prices, where prices[i] is the price of a stock on day i. You may complete as many buy and sell transactions as you like, but you can hold at most one share at a time, and after you sell you must wait one full day (a cooldown) before buying again. Return the maximum profit.
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries buy, sell or wait on every day, which is exponential. Instead, describe the end of each day by a state machine. State: hold is the best profit while owning a share, sold is the best profit if we sold today (so tomorrow is a cooldown), and rest is the best profit with no share and free to buy. Recurrence: hold = max(hold, rest - price) (keep holding or buy today, only allowed from rest), sold = hold + price (sell the share we had yesterday), rest = max(rest, sold) (stay resting or finish yesterday's cooldown). Base case: before day 0, hold = -infinity, sold = 0, rest = 0. The answer is max(sold, rest) since ending with a share never helps.
Algorithm
- Start with
hold = -inf,sold = 0,rest = 0. - For each price, compute the new values from the old ones:
newHold = max(hold, rest - p),newSold = hold + p,newRest = max(rest, sold). - Assign all three at once.
- Return
max(sold, rest).
O(n)Space: O(1)rest, never from sold; that single rule is the cooldown. A common follow-up replaces the cooldown with a transaction fee: then there are only two states and sold subtracts the fee.class Solution: def maxProfit(self, prices: List[int]) -> int: hold = float("-inf") # owning a share sold = 0 # sold today, so tomorrow is a cooldown rest = 0 # no share and free to buy for p in prices: hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold) return int(max(sold, rest))