Buy one day, sell on a later day, for the biggest profit. Walk the prices once, remembering the cheapest day so far.
▼The problem
LeetCode 121 (Easy). Given a list of prices, one per day, buy on one day and sell on a later day for the biggest profit; if no trade makes money, the answer is 0.
Example: [9, 4, 8, 2, 5, 7, 3] → **5** (buy at 2 on day 4, sell at 7 on day 6).
The solution
def max_profit(prices):
low, best = prices[0], 0
for p in prices:
low = min(low, p)
best = max(best, p - low)
return bestTranscript
Best Time to Buy and Sell Stock. You get a list of prices, one per day. Buy one day, sell on a later day, for the biggest profit. If prices only fall, the answer is zero.
Take nine, four, eight, two, five, seven, three. The highest price, nine, comes first, so you can't sell there. The best trade is buy at two, sell at seven: a profit of five.
The obvious way tries every buy day with every later sell day: about n squared pairs, slow for long lists.
Here's the trick. If you sell today, the best buy was the cheapest day before it. So walk once, remembering the lowest price so far. Today minus that low is today's best sale. Keep the biggest.
In code, low starts at the first price, best at zero. For each price, low becomes the smaller of the two, and best becomes today minus low, if that's bigger.
Day one, nine is the low. Four is lower: the flag moves. Eight minus four is four: best is four. Two is a new low; the flag drops again. Five minus two is three. Seven minus two is five: a new best. Three minus two is one. The answer is five.
One pass, so the time is O of n. Two numbers to remember, so space is constant.
Remember the low, check today, keep the best. That's Best Time to Buy and Sell Stock.