Description
Maximize profit from daily prices using as many transactions as desired, holding at most one share. After selling, you must wait one day before buying again.
Solution
def max_profit(prices):
hold = -prices[0]
sold = float("-inf")
rest = 0
for price in prices[1:]:
hold, sold, rest = max(hold, rest - price), hold + price, max(rest, sold)
return max(rest, sold)Examples
Example 1
- Input
[[1,2,3,0,2]]- Output
3
Buy at 1, sell at 2, rest, buy at 0, sell at 2.
Example 2
- Input
[[1]]- Output
0
A single day cannot realize profit.
Example 3
- Input
[[3,2,1]]- Output
0
Skipping all trades is best.
Approach
Track three end-of-day states: holding, just sold, and resting. Buying can use only yesterday's resting state; selling uses yesterday's holding state. Update all states from their previous values.
Time & space
O(n) time and O(1) auxiliary space, where n is day count.