Maximum Profit from One Stock Purchase and a Later Sale
Company: Xiaohongshu
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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.
Overview: Given one stock's price on each of several consecutive days, compute the maximum profit from buying one share and selling it on a strictly later day, or zero if no trade makes money. It tests efficient reasoning over an array under large input bounds and careful handling of edge cases such as falling prices or a single day.
You are given the price of one stock on each of n consecutive days. prices[i] is the price on day i, with days numbered from zero.
You may buy one share on one day and sell that share on a strictly later day. A trade is one purchase on day i and one sale on day j with i < j, and its profit is prices[j] - prices[i]. At most one trade is allowed, and not trading is allowed and gives profit 0.
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. Return 0 if no purchase followed by a later sale makes money.
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.
The answer is at most 1000000000, which fits in a signed 32-bit integer, so no value in this problem exceeds 2^31 - 1: Java may use int and C++ may use int.
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.
Constraints
- 1 <= n <= 100000, where n is the length of prices
- 0 <= prices[i] <= 1000000000
- The answer is at most 1000000000, which fits in a signed 32-bit integer
- A trade is one purchase on day i and one sale on day j with i < j; at most one trade is allowed, and not trading is allowed and gives profit 0
Examples
Input: ([8, 3, 6, 2, 9, 4],)
Expected Output: 7
Explanation: Source example 1: buy at 2 on day 3, sell at 9 on day 4 for a profit of 7; no other pair gives more.
Input: ([9, 7, 4, 1],)
Expected Output: 0
Explanation: Source example 2 and the strictly decreasing case: every later price is lower, so not trading (profit 0) is best.
Hints
- The answer is never negative: not trading is always one of the allowed choices, so 0 is a floor on the result.
- For a fixed selling day, only one thing about the earlier days matters when you want the largest difference.
- The order of days is what makes this more than max(prices) - min(prices): the cheapest day can come after the most expensive one.