Easy Greedy Choice Greedy
In plain English: Find the best day to buy and the best day to sell a stock to make the most money.
Track the minimum price seen so far. At each day, the best you can do is sell at today's price minus the cheapest buy — one pass, O(1) space.
Prompt
Given an array of stock prices (one per day), find the maximum profit from one buy and one sell (buy before sell).
Try to write it from scratch before scrolling down.
Solution
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for p in prices:
min_price = min(min_price, p)
max_profit = max(max_profit, p - min_price) # sell today, bought at min
return max_profit
# Test: max_profit([7,1,5,3,6,4]) == 5 (buy at 1, sell at 6)
# Test: max_profit([7,6,4,3,1]) == 0 (no profit possible)