Find the largest sum obtainable from a contiguous run of elements in an array.

Settle the empty case before writing anything

The question as usually asked is ambiguous in one way that decides your initialisation, so ask it: may the chosen run be empty? If it may, the answer for an all-negative array is zero, because taking nothing beats taking anything. If it may not — which is the usual intent, and the one every standard version of this problem assumes — then the answer for [-5, -2, -9] is -2, the least bad single element.

That is not pedantry. It is the difference between two initialisations, and the wrong one produces a function that looks correct on every example an interviewer gives verbally and is wrong on a case they will reach for immediately.

Extend or restart, and nothing else

At each element you face exactly one decision: does the best run ending here include the run ending at the previous element, or does it start fresh at this element? You never need to look further back than that, because any longer run ending here contains the run ending at the previous element as a suffix, and you have already computed the best of those.

function maxSubarraySum(nums) {
  // Not 0: the run must be non-empty, so seed with a real element.
  let best = nums[0];
  let endingHere = nums[0];

  for (let i = 1; i < nums.length; i += 1) {
    // Extend the previous run, or abandon it and start at nums[i].
    endingHere = Math.max(nums[i], endingHere + nums[i]);
    best = Math.max(best, endingHere);
  }

  return best;
}

Two variables and one pass. The recurrence is the whole algorithm, and stating it as a choice — extend or restart — is what an interviewer is listening for. A candidate who instead says "keep adding while the sum stays positive" has described the same behaviour by accident and will not be able to defend it on the input below.

The reset to zero, and the input that exposes it

The form almost everyone writes from memory is this:

let sum = 0, best = 0;
for (const n of nums) {
  sum += n;
  if (sum < 0) sum = 0;      // the reset
  best = Math.max(best, sum);  // best never drops below 0
}

On [-5, -2, -9] it returns 0. There is no empty run allowed, so the correct answer is -2, and nothing about the code looks wrong — best simply never falls below its initial value. Trace it: sum goes to -5 and resets to 0, then -2 and resets, then -9 and resets. best was 0 at the start and is 0 at the end.

This is worth dwelling on because of how it fails. It is correct on every array containing at least one positive element, which is every example anybody offers casually, so it survives testing by improvisation and dies on the first adversarial input. Seeding both variables from nums[0] and iterating from index 1 removes the failure entirely, without a special case for negatives.

The related slip is initialising best to 0 while computing endingHere correctly. The recurrence is then right and the answer is still clamped, which is harder to spot because the interesting part of the code is doing the right thing.

Recording where the run starts, not just that it ended

Returning the bounds is the usual follow-up, and the off-by-one lives in the start index rather than the end. The end is easy: it is wherever you improved best. The start has to be captured at the moment you restart, which is one branch earlier than the moment you record an improvement.

let best = nums[0], endingHere = nums[0];
let bestStart = 0, bestEnd = 0, currentStart = 0;

for (let i = 1; i < nums.length; i += 1) {
  if (endingHere + nums[i] < nums[i]) {
    endingHere = nums[i];
    currentStart = i;        // the restart, recorded here or lost
  } else {
    endingHere = endingHere + nums[i];
  }
  if (endingHere > best) {
    best = endingHere;
    bestStart = currentStart;
    bestEnd = i;
  }
}

Collapsing the branch back into Math.max is what loses currentStart, because the maximum tells you the value that won and not which of the two cases produced it. That is the trade: the compact version cannot report its own answer's location.

When the array does not fit on one machine

The distributed follow-up is where the linear scan stops being the whole story, and it is a genuine test of whether the candidate understands the recurrence or has memorised it. A chunk cannot just report its own best run, because the true best may straddle a boundary. Each chunk has to return four numbers: its total sum, its best run, the best run touching its left edge, and the best run touching its right edge. Combining two neighbours takes the better of their individual bests and the run formed by joining the left neighbour's right-edge run to the right neighbour's left-edge run.

That decomposition is associative, which is why it parallelises and why the same shape appears in segment trees. A candidate who reaches it has understood that the sequential version is a fold over exactly this state, compressed because a single pass never needs the left-edge value.