Why it works
- Any trade from day a to day b earns prices[b] − prices[a], which is the sum of the day-to-day changes in between. So one long trade over a climb earns exactly what its rises add up to.
- A trade that spans a drop pays for that drop. Leaving out every negative change and keeping every positive one is the largest sum the changes can give.
- Each rise is one trade of one day, and those never overlap, so this sum can really be earned with one share at a time.
Complexity
Time O(n): one pass over the days. Memory O(1): only profit and the current rise.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗