406. The Best Single Buy and Sell
Prices are given for n consecutive days. You may buy on one day and sell on
a LATER day, at most once. Print the largest profit possible, or 0 if no
profitable pair exists, since doing nothing is always allowed.
Trying every pair of days is O(n^2). The move to O(n) is to stop thinking
about pairs and fix the selling day instead.
If you sell on day i, the best you can do is to have bought at the lowest
price among days 0..i-1. That lowest price depends only on what came before,
so it can be carried along:
for each day:
best = max(best, price - lowestSoFar)
lowestSoFar = min(lowestSoFar, price)
The order of those two lines matters. Updating the lowest price first would allow buying and selling on the same day, which is not permitted and turns every answer into at least 0 for the wrong reason.
The answer is never negative, because not trading is allowed. So a falling market answers 0, and initialising the best profit to 0 rather than to negative infinity is correct here, unlike in problem 405.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ price ≤ 1000000`
Input
The first line contains an integer n.
The second line contains n space-separated prices.
Output
Print the largest profit from one buy followed by one later sell, or 0 if none is profitable.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.