Largest product of a contiguous run

Dynamic programming Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
vals = [-2, 3, -4]
hi = lo = best = vals[0]
for v in vals[1:]:
    hi, lo = max(v, hi * v, lo * v), min(v, hi * v, lo * v)
    best = max(best, hi)
print(best)

Options

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

Show answer

Answer: A 24

Right: the whole run, -2 × 3 × -4, is positive.

The smallest product (-6) becomes the largest after multiplying by -4, which is why both are carried.

Why not the others?
  • B 3. Tracking only the largest would stop at 3.
  • C 12. 3 × -4 is negative; the full run gives 24.

30-second answer

Track both the largest and the smallest product of a run ending at each position, because a negative value turns the smallest into the largest. At each value v, the new largest is the max of v, v × old largest and v × old smallest; likewise for the smallest. O(n) time, O(1) memory.

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

Explain the largest product run.

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

  • Track largest and smallest
  • Negatives swap them
  • O(n)

Deep dive

Carrying both extremes is the key idea; with sums only the largest matters.

A zero resets both to zero, and the next value starts a fresh run.

Python ints do not overflow, so long runs are safe.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def best_product(vals: list[int]) -> int:
    high = low = best = vals[0]  # extremes of runs ending here
    for v in vals[1:]:
        options = (v, high * v, low * v)
        high, low = max(options), min(options)  # a negative swaps them
        best = max(best, high)
    return best

Common mistakes

  • Tracking only the largest, which fails on [-2, 3, -4].
  • Updating the largest before computing the smallest from the old value.

Senior take & follow-ups

Give the [-2, 3, -4] example before the code; it explains why two values are needed.

Follow-up questions

Think of your answer first, then open the hint.

  1. How does this compare with the largest sum version?

    Show hint

    Sums need only the best run ending here; products need the best and worst because of sign flips.

  2. How do you return the run itself?

    Show hint

    Track the start index for each extreme and update it when a value starts fresh.

What each operation costs: Two Dimensional Arrays

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.