Not the exercise, just the habit it needs. This reports, for each day, the hottest temperature so far, without ever looking back at the earlier days.
temps = [14, 17, 12, 19, 16]
hottest = temps[0]
for day, temp in enumerate(temps):
hottest = max(hottest, temp)
print(day, temp, "hottest so far:", hottest)
# 0 14 hottest so far: 14
# 1 17 hottest so far: 17
# 2 12 hottest so far: 17
# 3 19 hottest so far: 19
# 4 16 hottest so far: 19
- The past, summed up in one number
Everything the loop needs to know about earlier days is in `hottest`. That is what lets one pass replace looking back over every earlier day.
- The order of the two lines matters
Update the running value before or after using it, and you get different answers. In the exercise the difference is whether you can sell on the day you bought.
- Start from real data
hottest starts at the first temperature, not at 0. Starting at 0 would break the moment every temperature was below freezing.
If today is the day you sell, which earlier day should you have bought on? You only need one number from the past to answer that.
Walk through the prices keeping two things: the cheapest price so far, and the best profit so far. Each day could be a better day to sell, or a new cheapest day.
Check for a negative price first. cheapest starts at infinity, best at 0. For each price: best = max(best, price - cheapest), then cheapest = min(cheapest, price). Selling first, then updating the low, stops a same-day trade.
def best_profit(prices): if any(price < 0 for price in prices): raise ValueError('a price cannot be negative') cheapest = float('inf') best = ____ for price in prices: best = max(best, price - ____) cheapest = ____(cheapest, price) return best
def best_profit(prices):
if any(price < 0 for price in prices):
raise ValueError("a price cannot be negative")
cheapest = float("inf")
best = 0
for price in prices:
best = max(best, price - cheapest)
cheapest = min(cheapest, price)
return best
Starting cheapest at infinity handles an empty list with no special case: the loop never runs and best stays 0. prices[0] would need its own check first.
Not trading is always an option, so the answer can never be below 0. Starting best at 0 says that without an if at the end.
Why max minus min is wrong (the order of days), what the running minimum stands for (the best buy day so far), and that the answer takes one pass and two variables, whatever the length of the list.
Allow as many trades as you like and the problem becomes simpler, not harder: add up every rise from one day to the next. Limit it to two trades and it becomes a small dynamic-programming problem. The single-trade version is only the first of a family.
- Return the buy day and sell day as well as the profit.
- Allow any number of trades, one at a time, and find the total best profit.
- Charge a fixed fee on every sale, and see which answers change.