Best Time to Buy and Sell Stock

The chart has many pairs of days, but each sell day has only one purchase worth remembering.

Brute force — try every trade

Choose every buy day and test every later sell day. A negative difference never improves the answer, so starting best at zero handles falling prices naturally.

def max_profit(prices: list[int]) -> int:
    best = 0
    for buy in range(len(prices) - 1):
        for sell in range(buy + 1, len(prices)):
            best = max(best, prices[sell] - prices[buy])
    return best

Time O(n²) — you inspect every ordered buy/sell pair. Space O(1) — only the best profit is stored.

Cheapest buy so far — one pass

Treat each price as today's possible sale. The best purchase for that sale is the lowest price strictly before it, so carry that minimum forward while you scan.

def max_profit(prices: list[int]) -> int:
    cheapest = prices[0]
    best = 0
    for price in prices[1:]:
        best = max(best, price - cheapest)
        cheapest = min(cheapest, price)
    return best

Checking profit before updating cheapest keeps the time order honest. If today's price becomes the new minimum, it can only serve as a purchase for a later day.

The exchange argument is a proof that replacing a choice with the greedy choice can't make an answer worse. Fix any sell day in an optimal trade. If its purchase isn't the cheapest earlier day, exchange that purchase for the cheapest one; the sale stays legal and the profit can only rise. Therefore the cheapest earlier price is globally optimal for every possible sale, and taking the best of those sales is globally optimal overall.

Time O(n) — each price is visited once. Space O(1) — two numbers hold all the history you need.