Why it works
- If you sell on day i, the best buy is the lowest price before it. low keeps exactly that, so each day needs one subtraction, not a look back over all earlier days.
- A new low does not erase best: an earlier sale stays a valid trade. Here best keeps 6 while low drops to 2, and only the sale at 9 replaces it.
- The answer is not the highest price minus the lowest: the sale has to come after the buy. 10 comes before 2, and after 1 the price never climbs above 3.
Complexity
Time O(n): one pass over the days, constant work per day. Memory O(1): only low and best; the rows in the picture show their history.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗