skip to content

In Kadane's algorithm over signed sensor drift readings, why does clamping the running sum at zero break?

level: middleimportance: must knowfreq 66%

answer

  1. what window does the running value describe
  2. clamping at zero admits the empty window
  3. try a stream that is entirely negative
  4. the honest answer is the least-negative reading
  5. seed both variables from the first reading

basics

~20 s

Clamping the running sum at zero silently allows the empty window, so on readings that are all negative the scan returns 0 instead of the least-negative reading. Use running = max(reading, running + reading), seeded from the first reading.

solid answer

~50 s

The running variable in Kadane's algorithm is supposed to mean *the maximum sum of a window ending exactly at this reading*. Clamping it at zero replaces that with *the maximum sum of a window ending here, or nothing at all*, which quietly admits the empty window as a candidate answer. On a drift stream where every reading is negative, every window has a negative sum, so the clamped version reports 0 — a total no window produces — instead of the least-negative single reading. The fix keeps the invariant honest: `running = max(reading, running + reading)`, meaning either extend the previous window or start fresh at this reading, with `running` and `best` both seeded to `readings[0]` and the loop starting at index 1. Clamping is only correct when an empty window is explicitly a legal answer.

code

pseudocode · 10 lines
pseudocode
// readings: signed drift values, n >= 1
best = 0
running = 0
for i in 0..n-1
    running = running + readings[i]
    if running < 0
        running = 0
    if running > best
        best = running
return best

go deeper

for a junior

Be ready to name the one-pass linear scan for the largest contiguous sum and to say what it returns when every value is negative. Knowing that the answer is then the least-negative single value is the point being tested.

for a middle

State the running variable's meaning as a sentence before writing the update, then show how clamping at zero changes that sentence and therefore the answer. Seeding both variables from the first reading is part of the explanation.

for a senior

Treat it as a contract question: ask whether the empty window is legal, then pick the formulation that matches. Expect follow-ups on reporting window boundaries and on accumulator width at streaming scale.

for a principal

Own the failure mode rather than the loop: a routine that returns a number no window produces will silently mislead an alerting rule. Be able to say how such a convention gets pinned down in a spec and caught by a test that uses all-negative data.

## What the scan is computing A sensor emits signed drift readings over a day, and you want the hottest sustained anomaly: the contiguous window whose readings sum to the largest total. Kadane's algorithm answers this in one pass, O(n) time and O(1) extra space, and it does so by maintaining a single invariant. > `running` = the maximum sum of any window that **ends exactly at the current reading**. Given that invariant, the step is forced. A window ending at reading `i` either extends the best window ending at `i-1`, or it starts at `i`: `running = max(readings[i], running + readings[i])` and the answer is the maximum of `running` over all positions, tracked in a second variable `best`. Both are seeded to `readings[0]`, and the loop runs from index 1. ## Where the clamped version comes from, and what it changes The widely copied variant reads: add the reading, and if the running total drops below zero, set it to zero. That is not a different implementation of the same invariant — it is a different invariant: > `running` = the maximum sum of a window ending exactly here, **or zero if that is better**. Zero is the sum of the empty window. So the clamped version answers a different question: *the largest window sum, where the empty window is allowed*. When at least one reading is non-negative the two questions have the same answer, which is why the bug hides for so long — every test built from mixed-sign data passes. The divergence appears exactly when every reading is negative. Suppose the drift stream is `-7, -3, -9, -4`. Every non-empty window sums to something negative; the best one is the single reading `-3`. The honest formulation reports `-3`. The clamped formulation never lets `running` fall below zero, `best` starts at 0 and is never beaten, and it reports **0**. That number is not the sum of any window in the input. Downstream, an alerting rule that reads it as "peak drift 0, nothing happening" is precisely wrong on the day when everything drifted the same way. ## The two conventions, stated properly This is a specification question before it is a bug. Two contracts are defensible: 1. **Non-empty window required.** The answer is the maximum over all non-empty windows. Use `running = max(readings[i], running + readings[i])` and seed from `readings[0]`. On all-negative input, the answer is the maximum single reading. 2. **Empty window allowed.** The answer is the maximum over all windows including the empty one, so it is never below zero. Clamping is correct here, and seeding `best = 0` is correct too. The defect is not clamping; it is clamping while claiming contract 1. In an interview, saying "which convention do we want on all-negative input?" before writing the loop is worth more than the loop. ## Seeding, and the empty-input case Seeding `best` to zero is the same bug wearing a different hat: even with the correct `max(reading, running + reading)` step, an initial `best = 0` clamps the reported answer from below. Seed `best = readings[0]`. If the input can be empty, decide and document what an empty stream returns — there is no maximum window, so either reject it or return a sentinel; do not let it fall through to 0. ## Reconstructing the window Often the operator wants *when* the anomaly happened, not just its magnitude. Track two extra indices: keep a `start` that is reset to `i` whenever the `max` chooses `readings[i]` over `running + readings[i]` (a fresh window began), and when `running` beats `best`, record `bestStart = start` and `bestEnd = i`. That is still O(1) space and one pass. ## Cost and scale Time is O(n) with one comparison and one addition per reading; space is O(1), which matters because the scan is streaming — it never needs the history. At 10^9 readings the interesting risk moves from asymptotics to arithmetic: if each reading can reach 10^6 in magnitude, a running total can reach 10^15, which overflows a 32-bit signed accumulator. Overflow here is silent and produces a wrong maximum rather than an error, so choose a 64-bit accumulator (or a saturating/checked one) and reason about the bound explicitly. The comparison `running + readings[i]` is also where the overflow occurs first, before the value is ever stored. ## Related shapes The same invariant generalizes. Maximum-*product* windows need two running values, the largest and the smallest so far, because a negative reading swaps their roles. A minimum-sum window is Kadane with the comparisons flipped. A window with a length cap is no longer plain Kadane; that constraint pushes you toward a different technique family. What survives across all of them is the discipline of naming what the running variable means before writing the update, which is exactly the discipline the zero-clamp bug violates.

  • When is the zero-clamping version actually the correct one?
    When the empty window is an explicitly legal answer — for example a report defined as total gain, never below zero. Under that contract the empty window has sum 0, clamping enforces it, and seeding best to 0 is right. The defect is only clamping while claiming that a non-empty window must be returned; state the convention before writing the loop.
  • How would you also report where the hottest window starts and ends?
    Keep a candidate start index that resets to the current position whenever the maximum chooses the current reading over extending the previous window, since that is where a fresh window begins. When the running value beats the best seen, record the current candidate start and the current index as the best window bounds. Still one pass, still O(1) extra space.
  • At 10^9 readings, what fails before the asymptotics do?
    Arithmetic. With readings up to 10^6 in magnitude, a running total can reach 10^15, which silently wraps in a 32-bit signed accumulator and yields a wrong maximum with no error raised. Use a 64-bit or checked accumulator and bound the sum explicitly; the overflow appears inside the addition being compared, before anything is stored.

saying these in an interview costs you the question

  • Says the answer can never be negative
  • Seeds the best value to zero rather than the first reading
  • Treats clamping at zero as merely a style choice
  • Claims all-negative input is an unrealistic edge case
  • Cannot state what the running variable means

context

resolving links…