You know a stock's price for each of the coming days: prices[i] is the price on day i. You may trade as often as you like, with one rule: you can hold at most one share at a time. On any day you may buy one share (if you hold none), sell your share (if you hold one), or sell and then buy again on that same day. You start and should finish with no share.
Write max_profit(prices: list[int]) -> int that returns the largest total profit you can make. Doing nothing earns 0.
max_profit([7, 1, 5, 3, 6, 4]) # 7 buy at 1, sell at 5; buy at 3, sell at 6
max_profit([1, 2, 3, 4, 5]) # 4 buy at 1, sell at 5
max_profit([9, 7, 4, 1]) # 0 prices only fall
max_profit([3]) # 0
Constraints:
1 <= len(prices) <= 10^50 <= prices[i] <= 10^4
Aim for O(n) time and O(1) extra space.
Show hint
buying at the bottom of a climb and selling at its top earns exactly the same as trading every single day-to-day step of that climb.