17. Best Time to Buy and Sell Stock

Given the price of a stock on each of n days, find the maximum profit achievable from exactly one buy followed by one later sell. If no profit is possible, print 0.

Input: The first line contains an integer n. The second line contains n space-separated integers, the stock price on each day. Output: Print a single integer - the maximum profit from one buy and one later sell, or 0 if no profit is possible.

1 <= n <= 10^5

The buy day must always come BEFORE the sell day - tracking the minimum seen SO FAR (not the overall minimum of the whole array) is exactly what enforces this ordering constraint correctly.

Given a stock's price on each day, find the biggest profit you could make by buying once and selling once, later. Brute force: Check every possible pair of buy-day and later sell-day directly (two nested loops) and keep the best profit - this costs O(n²), too slow for large price histories. Optimised: You only ever need to know the LOWEST price seen so far to compute today's best possible profit if selling today - tracking that one running minimum lets you find the overall best profit in a single pass, no need to compare every pair.

Precompute a suffix-maximum array where suffixMax[i] holds the highest price occurring on day i or any later day, then for each possible buy day i, compute the profit as suffixMax[i+1] - price[i] and take the maximum over all buy days. This is correct because for a fixed buy day, the best possible sell day is whichever later day has the highest price, which the suffix array gives directly, and it avoids the brute force's repeated inner scan by precomputing all the needed 'best future price' values in one pass, at the cost of the extra array. Time: O(n) Space: O(n)

Scan the prices once while maintaining the minimum price seen so far and the best profit found so far; at each day, first update the best profit using price[i] minus the minimum-so-far, then update the minimum-so-far if the current price is lower. This is correct because the best profit for selling on any given day only ever depends on the lowest price that occurred at or before it, and tracking that running minimum as a single variable removes the need for the suffix array entirely, computing the answer in one forward sweep with only constant extra memory. Time: O(n) Space: O(1)

For every pair of days (i, j) with i occurring before j, compute the profit price[j] - price[i] from buying on day i and selling on day j, and keep track of the maximum such profit seen, defaulting to 0 if no pair yields a positive profit. This is correct because it directly evaluates every legal buy-then-sell combination, but comparing every pair of days means redoing a lot of comparisons that later approaches can avoid. Time: O(n^2) Space: O(1)

1. Walk through the prices left to right, keeping track of the LOWEST price seen so far. 2. At each day, imagine selling TODAY - compute today's price minus the lowest price seen so far. 3. Keep track of the best (largest) such profit seen across the whole scan. 4. That running best is your final answer.

Time: O(n) - one single pass through the price list. Space: O(1) - just two running trackers (lowest price so far, and best profit so far).

Test n = 1 (no sell possible, print 0), strictly decreasing prices (profit 0), and n = 10^5 for performance.

Be ready to immediately connect this to its 'at most two transactions' and 'as many transactions as you like' variants, both common, harder follow-ups building on this exact same running-minimum idea.