211. Best Single Stock Transaction

Why this mechanism works

Fix the sale day. The best compatible purchase is the cheapest earlier day, so the entire earlier prefix can be summarized by its minimum. Compare today's possible profit before adding today's price to that prefix. The best answer may also remain zero by choosing no transaction.

State and boundaries

lowest is the minimum price strictly before the current day. best is the greatest legal profit considered so far, including no trade.

Protocol

1. Initialize lowest to infinity and best to zero.
2. Compare today's sale price minus lowest with best.
3. Update lowest with today's price.
4. Return best.

Visualization

prices 7,1,5,3,6,4
cheapest earlier price before 6 is 1
profit 6-1=5; later 4 does not improve it

Python implementation

def stock_profit(prices):
    lowest, best = float('inf'), 0
    for price in prices:
        best = max(best, price - lowest)
        lowest = min(lowest, price)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 stock_profit: lowest, best = float('inf'), 0
prices=[7, 1, 5, 3, 6, 4]; lowest=inf; best=0

L3 stock_profit: for price in prices:
prices=[7, 1, 5, 3, 6, 4]; lowest=inf; best=0; price=7

L5 stock_profit: lowest = min(lowest, price)
prices=[7, 1, 5, 3, 6, 4]; lowest=7; best=0; price=7

L3 stock_profit: for price in prices:
prices=[7, 1, 5, 3, 6, 4]; lowest=7; best=0; price=1

L5 stock_profit: lowest = min(lowest, price)
prices=[7, 1, 5, 3, 6, 4]; lowest=1; best=0; price=1

L3 stock_profit: for price in prices:
prices=[7, 1, 5, 3, 6, 4]; lowest=1; best=0; price=5

L4 stock_profit: best = max(best, price - lowest)
prices=[7, 1, 5, 3, 6, 4]; lowest=1; best=4; price=5

L3 stock_profit: for price in prices:
prices=[7, 1, 5, 3, 6, 4]; lowest=1; best=4; price=3

L3 stock_profit: for price in prices:
prices=[7, 1, 5, 3, 6, 4]; lowest=1; best=4; price=6

L4 stock_profit: best = max(best, price - lowest)
prices=[7, 1, 5, 3, 6, 4]; lowest=1; best=5; price=6

L3 stock_profit: for price in prices:
prices=[7, 1, 5, 3, 6, 4]; lowest=1; best=5; price=4

L2 stock_profit: lowest, best = float('inf'), 0
prices=[7, 5, 3]; lowest=inf; best=0

L3 stock_profit: for price in prices:
prices=[7, 5, 3]; lowest=inf; best=0; price=7

L5 stock_profit: lowest = min(lowest, price)
prices=[7, 5, 3]; lowest=7; best=0; price=7

L3 stock_profit: for price in prices:
prices=[7, 5, 3]; lowest=7; best=0; price=5

L5 stock_profit: lowest = min(lowest, price)
prices=[7, 5, 3]; lowest=5; best=0; price=5

L3 stock_profit: for price in prices:
prices=[7, 5, 3]; lowest=5; best=0; price=3

L5 stock_profit: lowest = min(lowest, price)
prices=[7, 5, 3]; lowest=3; best=0; price=3

Why the solution is correct

For each sale day, choosing any earlier price above the prefix minimum cannot improve profit. The loop evaluates that day's optimal legal purchase and retains the maximum across all sale days. The zero initial result covers every unprofitable or empty case.

Time and space

O(n) time and O(1) auxiliary state.

Common mistakes

Using the global minimum without chronology may buy after selling. Summing all positive daily changes solves the multiple-transaction variant.

Reasoning card

Transfer exercise

Return purchase and sale indices with an explicit tie rule while preserving the same prefix-minimum summary.