Pattern visualizer
Best Time to Buy and Sell Stock
You must buy BEFORE you sell, so the best sell at day i pairs with the cheapest price seen up to day i. One sweep keeps two numbers: minPrice (cheapest so far — the ideal buy day behind us) and best (largest sell-minus-min ever seen). Each day either lowers the buy floor or tries a sell against it — no nested loops needed. Animated on: Given daily prices [7, 1, 5, 3, 6, 4], pick one day to buy and one later day to sell for maximum profit..
One pass: track min price so far, bank the best profit
time O(n)space O(1)step 1 / 8
7
[0]1
[1]5
[2]3
[3]6
[4]4
[5]line 2
Day 0: price 7 is the only price seen, so minPrice = 7 and best = 0 (selling day 0 with no earlier buy earns nothing). min marks the cheapest buy day so far.
Pseudocode
1FUNCTION maxProfit(prices):2 minPrice = prices[0]3 best = 04 FOR i from 1 to (length of prices) - 1:5 IF prices[i] < minPrice:6 minPrice = prices[i]7 ELSE:8 best = the larger of best and (prices[i] - minPrice)9 RETURN best
← / → step · space play · Home restart