Maximum Profit from One Stock Purchase and a Later Sale

You are given the price of one stock on each of n consecutive days. You may buy one share on one day and sell that share on a strictly later day. Return the largest profit you can make, or 0 if no purchase followed by a later sale makes money.

Function Signature

def max_single_trade_profit(prices: list[int]) -> int:

Rules

• prices[i] is the price on day i, with days numbered from zero.
• A trade is one purchase on day i and one sale on day j with i < j. Its profit is prices[j] - prices[i].
• At most one trade is allowed. Not trading is allowed and gives profit 0.
• This exercise uses the single-trade version of the stock buy-and-sell problem. Multiple trades, transaction fees, cooldown periods, and short selling are out of scope.

Output

Return one integer: the maximum profit over all allowed choices, including not trading. The answer is therefore never negative, and it is unique even when several pairs of days achieve it.

Constraints

• 1 <= n <= 100000
• 0 <= prices[i] <= 1000000000
• The answer is at most 1000000000, which fits in a signed 32-bit integer.

Examples

Example 1

Input: prices = [8,3,6,2,9,4]
Output: 7

Buying at price 2 on day 3 and selling at price 9 on day 4 gives 7. No other pair of days gives more.

Example 2

Input: prices = [9,7,4,1]
Output: 0

The price only falls, so not trading is best.

Example 3

Input: prices = [2,4,1,3]
Output: 2

Days 0 and 1, and days 2 and 3, both give a profit of 2. Only the value is returned.

Maximum Profit From a Single Stock Trade

Hints

1. The answer is never negative: not trading is always one of the allowed choices, so 0 is a floor on the result.
2. For a fixed selling day, only one thing about the earlier days matters when you want the largest difference.
3. The order of days is what makes this more than max(prices) - min(prices): the cheapest day can come after the most expensive one.

Approach

Algorithm: scan the days once from left to right, keeping two running values: min_price, the smallest price seen strictly before the current day, and best, the largest profit found so far (initialized to 0 because not trading is always allowed). At day i >= 1, first score the candidate trade that sells on day i: profit = prices[i] - min_price. Update best if that profit is larger. Only afterwards is prices[i] folded into min_price, which guarantees the buying day is strictly earlier than the selling day.

Invariant: after processing index i, min_price = min(prices[0..i]) and best = max(0, max over pairs j < k <= i of prices[k] - prices[j]).

Correctness: any legal trade sells on some day k >= 1 and buys on some day j < k. For a fixed selling day k, the best achievable profit is prices[k] - min(prices[0..k-1]), because subtracting the smallest earlier price maximizes the difference. The loop evaluates exactly that quantity for every k, and the maximum over all k, floored at 0 for the not-trading option, is the answer. Since every candidate is considered and no illegal pair (j >= k) is ever scored, the returned value is both achievable and maximal.

Edge cases: a single-day list never enters the loop and returns 0, since no strictly later selling day exists; an empty list (outside the stated domain) is guarded and also returns 0. All-equal or strictly decreasing prices leave best at 0 rather than returning a negative number. The global minimum may occur after the global maximum, so the answer is not max(prices) - min(prices); the ordered scan handles that. With 0 <= prices[i] <= 1000000000 and an answer of at most 1000000000, every intermediate difference lies in [-1000000000, 1000000000], so 32-bit signed arithmetic is sufficient in Java and C++ and JavaScript numbers stay exact.

• Time complexity: O(n)
• Space complexity: O(1)