Best Time to Buy and Sell Stock

Buy once, then sell later. Return the largest profit.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Best Time to Buy and Sell Stock: For each possible selling day, subtract the lowest price in its scanned prefix and preserve the largest profit.

Input and goalBuy once, then sell later. Return the largest profit.

Initialize from infinityOn day 0 price 7, lowest=min(infinity,7)=7 and best=max(0,7-7)=0.

lowest earlier buyselling day701152336445

scannedPrefix[0..0]arithmeticlowest=7; profit=7-7=0; best=0

Recognize it

Use a running minimum when an ordered one-pass problem asks for the best later-minus-earlier difference and the buy or baseline must occur before the current item.

Keep true

After each day, lowest is the minimum price in the scanned prefix and best is the largest valid sell-minus-earlier-buy profit whose selling day lies in that prefix.

Reuse it

For maximum ordered differences, summarize the best earlier baseline while treating each new value as the right endpoint; analogous scans find maximum rise, minimum spread, and best prefix-relative gain.

Pattern: Running minimum.

Simple idea: For each selling price, the best earlier buy is the lowest price seen so far. Update that lowest price and the best profit as you scan.

def max_profit(prices: list[int]) -> int:
   lowest = float("inf")
   best = 0

   for price in prices:
      lowest = min(lowest, price)
      best = max(best, price - lowest)
   return best

Cost: $O(n)$ time and $O(1)$ space.