Best Time to Buy and Sell Stock

The machine gets one pass over an array of daily prices and must find the single buy/sell pair with the maximum profit — buy before sell, one transaction only. Brute force pairs every buy with every later sell: O(n²). The insight: at any moment, the best possible sale today is price - min_price_so_far. Track the minimum as you go; you never need to look back.

def max_profit(prices):
    min_price = float("inf")
    profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > profit:
            profit = price - min_price
    return profit

Steps: (1) keep a running minimum, (2) for each price compute the profit if sold today, (3) keep the largest profit seen.

Time is O(n), one pass. Space is O(1) — just two integers.

Trickiest edge case: a monotonically falling array like [7,6,4,3,1]. The best transaction is no transaction, so profit stays 0 — the answer is never negative, and there is no forced trade. A single-day array returns 0 for the same reason.