Problem. Given daily stock prices, find the maximum profit from one buy-then-sell transaction. Return 0 if no profit is possible.
Examples:
[7, 1, 5, 3, 6, 4]→5— buy at 1, sell at 6.[7, 6, 4, 3, 1]→0— prices only decrease.[1, 2]→1[2, 4, 1]→2— buy at 2, sell at 4 (not at 1 which comes after the peak).[3]→0— can’t transact with one price.
Solution. Track the running minimum price seen so far; at each day, the candidate profit is price - min_so_far.
def max_profit(prices):
best = 0
lo = float("inf")
for p in prices:
lo = min(lo, p)
best = max(best, p - lo)
return best
O(n) time, O(1) space.
Gotchas.
- You must buy before you sell — you can’t sell on the same day you buy (or before).
- A strictly decreasing price list gives profit 0, not a negative number.
- Single-element list: no transaction possible, return 0.
- This is equivalent to maximum subarray on the array of daily returns.