Largest total of a contiguous run

Greedy choices and intervals Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
vals = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
run = best = vals[0]
for v in vals[1:]:
    run = max(v, run + v)
    best = max(best, run)
print(best)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 6

Right: the run 4, -1, 2, 1 adds up to 6.

A run is worth keeping only while its total is positive, which is the choice the max() makes each step.

Why not the others?
  • B 7. Extending to include the 4 at the end adds -5 first.
  • C 4. Extending 4 through -1, 2 and 1 does better.

30-second answer

Keep the best total of a run ending at the current value: either extend the previous run or start fresh here, whichever is bigger. Track the best seen overall. One pass, O(n) time, O(1) memory. This is Kadane's algorithm.

Practise saying it · 30 s. No recording, just a timer

Explain the best run total.

Say your answer out loud, then check which of these points you covered:

  • Extend or start fresh
  • Track the best
  • O(n)

Deep dive

Starting fresh whenever the running total would be worse than the value alone is the whole greedy rule.

Initialise with the first value, not 0, so all-negative lists work.

The same idea on prefix sums: best = max over i of prefix[i] - min earlier prefix.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def best_run(vals: list[int]) -> int:
    run = best = vals[0]
    for v in vals[1:]:
        run = max(v, run + v)  # keep the run only while it helps
        best = max(best, run)
    return best

Common mistakes

  • Starting the best at 0, which returns 0 for all-negative input such as [-3, -1, -2].
  • Resetting to 0 after adding the current value (run = max(run + v, 0)), which also reports 0 for [-3, -1, -2]. Resetting before adding, run = max(run, 0) + v, is a correct form of the same rule.

Senior take & follow-ups

Show the all-negative case; it proves your initialisation is right.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you return the run's start and end?

    Show hint

    Record the index where each fresh start happens and the end when the best improves.

  2. What about a circular list?

    Show hint

    The best is either a normal run or the total minus the most negative run (unless all are negative).

What each operation costs: Merge Sort · Quick Sort

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.