How do you find the maximum profit from a single buy and sell, and why is the greedy approach correct?
You keep the lowest price that you have seen so far, and you work out the profit at each step.
So why is that greedy approach correct? Because for any day that you sell on, the best price to have bought at is the lowest price on some earlier day. So if you are going to sell today, then the best you can do is to have bought at the lowest price you have seen up to now. So all you have to do is keep track of that lowest price and of the best difference you have found.
def max_profit(prices):
best = 0
lowest = prices[0]
for price in prices[1:]:
if price - lowest > best:
best = price - lowest
if price < lowest:
lowest = price
return best
And the reason that you do not have to try every pair is that the lowest price you have seen covers all of them at once. Any pair that starts on an earlier day and ends on today makes a profit of today's price minus that earlier price, and the lowest price gives you the biggest of them.
So it is O of n for the time and O of 1 for the space, because you never look at the past prices again.
The last question in this topic shows the function and the case that trips people up.