Back to solutions

Best Time to Buy and Sell Stock

EasyArrays

Choose one buy day and a later sell day to maximize profit.

Open problem
Constraints
  • 1 <= n <= 10^5
  • 0 <= prices[i] <= 10^4

Track the minimum so far

Time O(n)Space O(1)

The best day to have bought before today is the cheapest day seen so far. Keep that running minimum; the best profit ending today is today's price minus that minimum. Update both as you scan once from left to right.

Key terms
running minimum:
The smallest value seen from the start up to the current position, updated as you go.
profit ending today:
The best money you could make if you are forced to sell on the current day: price today minus the cheapest earlier price.
int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX, best = 0;
    for (int p : prices) {
        minPrice = min(minPrice, p);
        best = max(best, p - minPrice);
    }
    return best;
}
Step by step
  1. Initialize minPrice to a very large number and best to 0.
  2. For each price p, first update minPrice = min(minPrice, p) so it holds the cheapest buy price up to now.
  3. Then compute p - minPrice, the profit if you sell today, and update best = max(best, p - minPrice).
  4. Because minPrice only ever refers to an earlier day, the buy always happens before the sell.
  5. After the scan, best holds the maximum achievable profit (0 if prices never rose).