The problem
A line is split into sections. The list a holds the minutes each section gains (a positive number) or loses (a negative number) against the timetable. A stretch is a run of one or more neighbouring sections. Return the largest total of any stretch.
best_stretch([2, -5, 3, 4, -1, 2, -6, 1])
# 8, from the stretch 3, 4, -1, 2
best_stretch([-4, -2, -7])
# -2: a stretch has at least one value
The fast answer uses one pass. To trust it, you need a proof. Lesson 3’s induction gives one: assume you know the best stretch that ends at section i - 1, and show how to get the best stretch that ends at section i.
Limits
- Up to 200,000 values. The list has at least one value.
Builds on CORR-2 Loop invariants and CORR-3 Proof by induction.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Mixed gains and losses | Not run | |
| 2 | All positive | Not run | |
| 3 | All negative | Not run | |
| 4 | One value | Not run | |
| 5 | Best at the very end | Not run | |
| 6 | A big loss splits two gains | Not run | |
| 7 | Zeros | Not run | |
| 8 | 200,000 values | Not run |