Best Time to Buy and Sell Stock

Given daily prices of a stock, return the maximum profit you can achieve from exactly one buy and one sell. 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.

Function signature

func MaxProfit(prices []int) int

Inputs / outputs

• prices: prices[i] is the price on day i.
• Return: the maximum profit from one transaction.

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 from left to right:
   • Update best = max(best, p - minPrice).
   • Update minPrice = min(minPrice, p).
3. Return best.

Correctness sketch

• Invariant: after processing day i, minPrice is the minimum of prices[0..i], and best is the maximum profit achievable using days 0..i.
• The algorithm maintains a feasible best-so-far state while scanning.
• Each greedy update preserves feasibility and never discards a possible optimal answer.
• When the scan ends, the recorded state represents the optimal solution.

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

• Updating minPrice before computing p - minPrice (breaks the invariant).
• Forgetting that no profit is allowed -> return 0.

Complexity

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

Implementation notes (Go)

• Use integers; no floating-point needed.