Not the exercise, just the move it is built on. This counts a streak of dry days, and a rainy day resets it, because a streak that has been broken is no use to whatever comes next.
rain_mm = [0, 0, 3, 0, 0, 0, 1, 0]
streak = longest = 0
for mm in rain_mm:
streak = streak + 1 if mm == 0 else 0 # carry on, or start again
longest = max(longest, streak)
print(longest) # -> 3
- Carry on or start again
At every step the question is the same: is the run so far worth keeping? For dry days, a rainy day says no. For sums, a run that has gone below zero says no.
- Keep the best separately
The current streak goes up and down; `longest` only goes up. You need both, because the best run may be long finished by the end.
- Where the running values start
Zero is right for counting days. For sums that can all be negative, starting the best at zero invents a run that was never there.
Walk the list keeping the best total of a run that ends exactly here. For the next number, is it better to add it to that run, or to start a new run with it alone?
current = max(number, current + number). Keep a separate best, updated every step, and start both from the first number, not from 0.
Raise for an empty list. current = best = changes[0]. For every number after the first: current = max(number, current + number); best = max(best, current). Return best.
def best_run(changes): if not changes: raise ValueError('no days') current = best = changes[____] for number in changes[1:]: current = max(____, current + number) best = max(best, ____) return best
def best_run(changes):
if not changes:
raise ValueError("there are no days to choose from")
current = best = changes[0]
for number in changes[1:]:
current = max(number, current + number)
best = max(best, current)
return best
If the run so far is negative, adding it makes things worse, so the new number starts a run of its own. If it is positive, it is always worth carrying. One comparison says both.
It is why an all-negative month gives -1 rather than 0: the best is always a real run, never the empty one.
The sentence "a negative running total can only hurt what follows", the all-negative edge case, and linear time with two variables.
If the question allows an empty run, so that zero is a valid answer, start best at 0 instead, and say out loud that you are doing it on purpose. If it asks for the run itself, track where the current run started; the totals alone do not tell you.
- Return the first and last day of the best run as well as its total.
- Find the best run of exactly seven days, and compare the code with this one.
- Treat the month as a circle, so a run can wrap from the last day round to the first.