Best Time to Buy and Sell Stock

Given daily prices of a stock, return the maximum profit you can achieve from at most one buy followed by one sell on a later day. If no profit is possible, return 0.

The naive O(n^2) approach checks all buy/sell pairs. A single scan with a running minimum is enough.

Why this is worth learning

The time ordering matters: a sale can use only an earlier purchase. A running minimum summarizes every possible earlier buy without enumerating pairs.

Before coding: one-minute experiment

For [5,4,7,1,3], what is the maximum single-trade profit, and why is 7-1 invalid?

Function signature

func MaxProfit(prices []int) int

Inputs / outputs

• prices: prices[i] is the price on day i.
• Return: the maximum profit from at most one transaction; choosing no trade earns 0.

Example

prices = [7,1,5,3,6,4]
Output: 5

Buy at 1, sell at 6.

Constraints

• 1 <= len(prices) <= 100_000
• 0 <= prices[i] <= 1_000_000_000

Core idea (near-solution)

Track the lowest price so far and the best profit so far.

Invariant: after processing day i, minPrice is the minimum of prices[0..i], and best is the maximum profit achievable using days 0..i.

Algorithm (step-by-step)

1. Initialize minPrice = prices[0], best = 0.
2. For each price p after the first day, from left to right:
   • Update best = max(best, p - minPrice).
   • Update minPrice = min(minPrice, p).
3. Return best.

Correctness sketch

Before processing a possible sale day, the minimum price summarizes all earlier purchase days, and best is the largest nonnegative profit already considered. Every legal trade ending on this day is maximized by the cheapest earlier purchase. Comparing that profit with best therefore accounts for all trades ending here. Updating the minimum prepares the invariant for the next day. Initializing best to zero also represents choosing no trade. After the last day, every legal sale has been considered. Updating the minimum first is also safe in this no-fee variant because it only adds a zero-profit same-day candidate.

Trace (hand walkthrough)

Example input:
prices = [7,1,5,3,6,4]
Output: 5

Buy at 1, sell at 6.

Walk:
- start min=7, best=0
- price=1 -> min=1, best=0
- price=5 -> best=max(0,5-1)=4
- price=3 -> best=4
- price=6 -> best=max(4,6-1)=5
- price=4 -> best=5

Pitfalls to avoid

• Subtracting the global minimum from the global maximum without checking their time order. Updating the running minimum first is safe here: it adds only a zero-profit same-day candidate.
• Forgetting that no profit is allowed -> return 0.

Debugging lens

A decreasing sequence should return zero, not a negative profit. [5,4,7,1,3] catches implementations that subtract the global minimum from the global maximum without respecting dates.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Use integers; no floating-point needed.

Reconstruction checkpoint

For [5,4,7,1,3], what is the maximum single-trade profit, and why is 7-1 invalid?

Return to Array & String · Module quiz