• 1 ≤ prices.length ≤ 10⁵
• 0 ≤ prices[i] ≤ 10⁴
• At most one buy and one sell, and the sell must come after the buy
• Doing nothing is permitted, so the answer is never negative

Pick a day to buy and a strictly later day to sell, and maximise sell price − buy price. You may also decline to trade at all, which is why the floor is 0 rather than a negative number. On a strictly falling market like [7, 6, 4, 3, 1], every possible trade loses money, so the answer is 0.

Note carefully: this is not "biggest number minus smallest number". On [2, 9, 1] the smallest is 1 and the largest is 9, but the 9 comes before the 1, so that pair is not a legal trade. The best legal trade is buy at 2 and sell at 9, for 7. Order is part of the constraint, and every wrong solution to this problem ignores it in some way.

Try every pair of days with the buy first:

def max_profit(prices):
    best = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            best = max(best, prices[j] - prices[i])
    return best

Count it: day 0 is compared against n-1 later days, day 1 against n-2, and so on, giving about N²/2 comparisons. With prices up to 100000 days, that is five billion — far too slow.

It is slow because it treats every pair as its own puzzle. But the real decision is per day: on each day I either own the share or I do not, and that alone decides what I can do next. Walk the days once, tracking that, and the pairs take care of themselves.

Walk the days one at a time. Standing on day i, I am in one of two situations:

So besides the day, the thing that decides my options is: am I holding the share?

What can I do on day i?

The single-trade rule lives in one place: selling ends the trade (it never loops back to buy again), and buying starts from zero.

Base case: past the last day (i == n) there is nothing left to earn, so f = 0. The answer is f(0, not holding).

Write the story down exactly. holding is a boolean:

def max_profit(prices):
    n = len(prices)

    def f(i, holding):
        if i == n: return 0
        if holding:
            return max(prices[i], f(i + 1, True))        # sell (trade done), or keep
        else:
            return max(-prices[i] + f(i + 1, True),      # buy today
                       f(i + 1, False))                  # wait

    return f(0, False)

Correct, but exponential — each day branches in two. Yet there are only n × 2 different (i, holding) questions, so memoise: solve each once, reuse after.

def max_profit(prices):
    n = len(prices)
    memo = {}

    def f(i, holding):
        if i == n: return 0
        if (i, holding) in memo: return memo[(i, holding)]
        if holding:
            best = max(prices[i], f(i + 1, True))
        else:
            best = max(-prices[i] + f(i + 1, True), f(i + 1, False))
        memo[(i, holding)] = best
        return best

    return f(0, False)

O(N) time and space.

Turn it into a table. Let dp[i][h] hold what f(i, h) returned. Each recurrence line becomes an array assignment. Every read is from day i+1, so fill from the last day backwards, starting with day n all zeros. The answer is dp[0][0]:

def max_profit(prices):
    n = len(prices)
    dp = [[0, 0] for _ in range(n + 1)]      # dp[i][0] = not holding, dp[i][1] = holding

    for i in range(n - 1, -1, -1):
        dp[i][1] = max(prices[i], dp[i + 1][1])                    # holding: sell or keep
        dp[i][0] = max(-prices[i] + dp[i + 1][1], dp[i + 1][0])    # empty: buy or wait

    return dp[0][0]

Each day reads only day i+1, so two variables replace the whole table:

def max_profit(prices):
    next_hold, next_free = 0, 0             # dp[i+1][1], dp[i+1][0]
    for p in reversed(prices):
        hold = max(p, next_hold)                    # sell today, or keep
        free = max(-p + next_hold, next_free)       # buy today, or wait
        next_hold, next_free = hold, free
    return next_free

O(N) time, O(1) space.

Answer free = 5, buying at 1 and selling at 6.

And the falling market [7, 6, 4, 3, 1]: every buy costs more than any later sell, free never rises above 0, and the answer is 0 — we decline to trade.

The move that solved this is the one to keep: when the day alone is not enough, ask what decides your options and add exactly that to the state. Here it was a single yes/no — am I holding the share? — and everything else followed the usual ladder: write the recursion straight from the two cases, memoise it, turn it into a table, then trim to two variables.

That two-state view is what carries into the harder variants. The rest of this family — cooldowns, fees, at most k transactions — keeps the same skeleton and only grows the state. Learn this version properly and the rest is bookkeeping.