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) {
let best = nums[0];
let endingHere = nums[0];
for (let i = 1; i < nums.length; i += 1) {
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 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;
best = Math.max(best, sum);
}
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;
} 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.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).