Best Time to Buy and Sell Stock

Problem

You are given an array prices where prices[i] is the price of a single share on day i. You may make at most one purchase and at most one sale, and the sale must happen on a later day than the purchase. Return the maximum profit you can achieve. If no profitable trade exists, return 0.

• prices holds up to about a hundred thousand daily prices.
• Each price is a non-negative integer, at most a few tens of thousands.

Examples

• prices = [9, 3, 8, 2, 9, 5] → 7. Buy at 2 on day 3, sell at 9 on day 4. Selling at the first 9 is not allowed because day 0 is before any buy.
• prices = [8, 7, 5, 4, 2] → 0. Prices only fall, so the best move is to not trade.
• prices = [3, 6, 1] → 3. Buy at 3, sell at 6; the later 1 cannot be sold after.

Hints

1. For each potential sell day, which buy day gives the most profit? You only need one number to summarize all earlier days.
2. Sweep left to right keeping the lowest price seen so far.
3. One pass: best = max(best, price - min_so_far), updating min_so_far as you go. This is Kadane's algorithm on daily price differences.