Description
Buy once and sell on a later day to maximize profit. Return zero if no profitable trade exists.
Solution
def max_profit(prices):
low, best = float('inf'), 0
for price in prices:
best = max(best, price-low)
low = min(low, price)
return bestExamples
Example 1
- Input
[[9,2,6,1,5]]- Output
4
Buying at 2 and selling at 6 earns 4; buying at 1 and selling at 5 ties.
Example 2
- Input
[[5,4,2]]- Output
0
Prices only decrease.
Example 3
- Input
[[3]]- Output
0
A sale on a later day is impossible.
Approach
Keep the cheapest earlier price and the best profit seen so far.
Time & space
O(n) time; O(1) space. Here n is the input length.