Easy Kadane's Variant Sliding Window
In plain English: Find the best day to buy and the best later day to sell a stock to maximize your profit.
Track the minimum price seen so far and compute profit at each step. This is Kadane's algorithm in disguise — the max gain ending here is today's price minus the running minimum.
Prompt
Given an array prices where prices[i] is the price of a stock on the ith day, return the maximum profit you can achieve from one buy and one sell. You must buy before you sell.
Try to write it from scratch before scrolling down.
Solution
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price) # track cheapest buy
max_profit = max(max_profit, price - min_price) # best sell
return max_profit
# Test: max_profit([7,1,5,3,6,4]) == 5 (buy@1, sell@6)
# Test: max_profit([7,6,4,3,1]) == 0 (no profit possible)