Best Time to Buy and Sell Stock

Scan the prices once, keeping two values: the lowest price seen so far and the best profit found so far. At each price, consider selling today and buying at that lowest price. If the difference beats the best profit, update it. Then update the lowest price if today's price is lower.

The greedy argument is that the cheapest buying point must be earlier than the selling point, so while scanning forward you always know the optimal buy price for today. Any pair of days can be expressed as a selling day and the cheapest day before it, so by tracking the running minimum you implicitly consider the best partner for every possible selling day in one pass.

The order of operations matters in the code. You must compute the profit before you update the lowest price, otherwise a day could be treated as both the buy and the sell, which for a single-element array would produce a profit from buying and selling the same day.

The trade-off to name is that this handles exactly one transaction. If the interviewer allows multiple buys and sells, the algorithm changes to adding every positive difference between consecutive days, which is also a single pass. Stating which variant you solved, and how the others would change, is what separates a memorised answer from understanding.

Complexity-wise, the single-transaction version is O of n time and O of 1 space, and it is strictly better than the quadratic approach that tries every pair of days. The only reason you would ever choose the quadratic version is if you needed the actual buy and sell dates, which the greedy scan can also provide with two extra variables.

The single pass keeps the cheapest price seen so far and the best profit found so far. On a falling series no sale can beat the price you already paid, so the profit stays at zero, which is the signal that no profitable transaction exists.

def max_profit(prices):
    best = 0
    lowest = prices[0]
    for price in prices[1:]:
        if price - lowest > best:
            best = price - lowest
        if price < lowest:
            lowest = price
    return best

print(max_profit([7, 1, 5, 3, 6, 4]))
print(max_profit([7, 6, 4, 3, 1]))

The outputs are 5 and 0. In the first series the best trade buys at one, the lowest price, and sells at six, giving a profit of five. In the second series the price only ever falls, so no transaction can make money and the function returns zero.

Two implementation details are worth stating. The profit is computed before the lowest price is updated, so a day is never used as both the buy and the sell. And the initial best profit is zero rather than a negative number, which encodes the convention that doing nothing is allowed and is at least as good as losing money. If the problem requires a transaction, then a falling series should return a negative value, and you would initialise the best profit from the first possible profit instead.

The trade-off is the same as for Kadane's algorithm but applied to prices: this finds the maximum difference between a price and an earlier lower price, which is the same shape of problem with the same single-pass recurrence. The space cost is constant, and the time cost is a single scan, so this is the version to reach for whenever you can hold only one position at a time.