prices[i] is the price of one share on day i. You may trade as many times as you like, but:
- you hold at most one share at a time, so you must sell before buying again;
- the day after you sell, you must rest: no buying on that day.
Each day you can do at most one thing (buy, sell or nothing). Write max_profit_with_rest(prices: list[int]) -> int that returns the largest total profit you can make. Doing nothing at all earns 0.
max_profit_with_rest([1, 2, 3, 0, 2]) # 3 buy 1, sell 2, rest, buy 0, sell 2
max_profit_with_rest([3, 8, 1, 9]) # 8 buy 1, sell 9 (selling at 8 would force a rest on the day it costs 1)
max_profit_with_rest([2, 1, 4, 5, 2, 9, 7]) # 10 buy 1, sell 4, rest, buy 2, sell 9
max_profit_with_rest([7, 6, 4, 3, 1]) # 0
Constraints: 0 <= len(prices) <= 10^5, 0 <= prices[i] <= 10^4.
Trying every sequence of actions is exponential; aim for O(n) time and O(1) extra space.
Show hint
At the end of each day you're in one of three situations: holding a share, having just sold today, or free to buy. Track the best cash for each.