Why it works
- Four states cover every moment: holding the 1st share, after the 1st sale, holding the 2nd, after the 2nd sale. Each day a state either stays as it was or is entered from the state before it at today’s price, so its number is the best over every history that ends in it.
- buy2 = sell1 − p pays for the second share out of the first trade’s profit. That is how 2 → 6 and 3 → 9 (10) beat the single trade 2 → 9 (7): the dip from 6 to 3 is sold out of instead of sat through.
- The states are updated one after another on the same day, so a later one may read a value set today. That only adds a buy and a sell at the same price, which earn 0, so no profit is counted that is not there.
Complexity
Time O(n): one pass over the days, four updates on each. Memory O(1): four numbers, whatever the number of days.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗