prices[i] is a stock's price on day i. You may buy one share on one day and sell it on a later day. Return the largest profit you can make, or 0 if no trade makes money.
Buy on day 3 at 1 and sell on day 5 at 8. Selling at 9 on day 0 is not possible: it comes before any purchase.
The price never rises, so the best choice is not to trade.
Constraints
1 <= prices.length <= 10⁵0 <= prices[i] <= 10⁴The best sale on a given day is that day's price minus the lowest price on any earlier day.
Look at it from the selling side. Suppose you sell on day d. Which day should you have bought on? The cheapest day before d, of course: nothing else about the earlier days matters. So the best sale on day d makes prices[d] - (lowest price before d).
Time O(n)Space O(1)
The full walkthrough and code in five languages, free to read
7