Coding · Dynamic programming
Maximum Subarray Sum
- Appears on company lists
- Medium
- 1 source
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
Given an array of integers that may hold negatives and zeros, return the largest sum of any non-empty run of consecutive elements. For [-2,1,-3,4,-1,2,1,-5,4] the answer is 6, from the run 4,-1,2,1. The array holds up to 100,000 values, so adding up every possible run separately is too slow. This is a guide level question: a prep guide names it as its example array problem for Zerodha, and no candidate report of it was found.
Restated in our own words, not a quote from Zerodha or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
First I would be straight about the source: one prep guide names Kadane's algorithm as its example array question for Zerodha, but no candidate report of it turned up, so treat it as a standard question worth knowing cold, not as something reported. Then I would pin the problem down. Must the run be non-empty? (Yes, so an all-negative array answers with its largest single element, not 0.) Do I return only the sum or also the positions? Can values be zero or negative? How large can the array get, and can the total overflow?
Assumptions I would state: the array has at least one element, the run needs at least one element, only the sum is returned, and totals stay inside a JavaScript number, which is exact up to about nine quadrillion.
Brute force
Say the obvious answer and why it is too slow.
Try every start and every end and add up the run between them. Re-adding each run from scratch is O(n³). Keeping a running sum while the end moves right makes each new end cost one addition, which brings it to O(n²), about five billion additions at n = 100,000. That is too slow.
The waste is that the best run ending at position i is closely related to the best run ending at i-1, yet the double loop rebuilds it from every possible start. Prefix sums describe the same waste: the best run ending at i is the prefix up to i minus the smallest earlier prefix, and that smallest prefix can be carried along instead of searched for each time.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²), or O(n³) if each run is re-added
- Time
- O(n)
- Space
- O(1)
The pattern is a running best that ends here, known as Kadane's algorithm, and it is one-dimensional dynamic programming. Let ending[i] be the largest sum of a run that must end exactly at index i. A run ending at i is either the single element nums[i] or a run ending at i-1 extended by nums[i], so ending[i] = max(nums[i], ending[i-1] + nums[i]). The answer is the largest ending[i], because the best run has to end somewhere.
Read the max as a decision. If the best run ending at i-1 is negative, extending it can only lose value, so drop it and start fresh at i. If it is zero or positive, keep extending. The decision depends only on ending[i-1], so one variable replaces the whole array and the space is constant.
Why is it correct? By induction, ending[i-1] is exactly the best run ending at i-1. Every run ending at i is either the lone element or some run ending at i-1 plus nums[i]. Adding the same number to every candidate keeps the best candidate on top, so the larger of the two options is the best run ending at i. Taking the maximum over all end positions then covers every possible run.
Out loud: "At each element I either start over or extend, whichever is larger, and I remember the biggest value I have seen." Start both variables at the first element, not at zero, so an all-negative array returns its largest element instead of 0.
Walk it through
A dry run on the example, step by step.
| Index | Value | Best ending here | Best so far |
|---|---|---|---|
| 0 | -2 | -2 | -2 |
| 1 | 1 | 1 | 1 |
| 2 | -3 | -2 | 1 |
| 3 | 4 | 4 | 4 |
| 4 | -1 | 3 | 4 |
| 5 | 2 | 5 | 5 |
| 6 | 1 | 6 | 6 |
| 7 | -5 | 1 | 6 |
| 8 | 4 | 5 | 6 |
Run it on [-2,1,-3,4,-1,2,1,-5,4]. Both variables start at the first element, -2. At index 1 the value 1 beats -2 + 1 = -1, so the running sum restarts at 1 and best becomes 1. At index 2, 1 + -3 = -2 beats -3, so the run keeps extending, but best stays 1.
Index 3 is the turning point: 4 beats -2 + 4 = 2, so a fresh start is better, and best becomes 4. Indexes 4 to 6 extend the run by -1, 2 and 1, giving 3, 5 and 6, and best reaches 6. Index 7 adds -5 and the running sum drops to 1, index 8 lifts it to 5, and neither beats 6. The answer is 6, from the run 4, -1, 2, 1.
The code
Runnable JavaScript, checked against test cases.
function maxSubarray(nums) {
let best = nums[0];
let running = nums[0];
for (let i = 1; i < nums.length; i++) {
running = Math.max(nums[i], running + nums[i]);
best = Math.max(best, running);
}
return best;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
All negative values: the answer is the largest single element. That works because both variables start at the first element and the restart option nums[i] is always available.
- Single element: the loop body never runs and that element is returned.
- Zeros: a zero can sit inside the best run or not without changing the sum, so ties are harmless.
- All positive values: the running sum never restarts and the answer is the total.
- Empty array: not valid input here, and the code would return undefined. Agree on 0, a thrown error or a guarantee of at least one element.
- Large totals: sums are exact in a JavaScript number up to about 9 quadrillion. In a language with 32-bit integers, use a 64-bit sum.
Follow-ups to expect
Where the interviewer pushes next.
- How would you also return the start and end positions of the best run, and which run would you report when two runs tie?
- How would the answer change if the array is circular, so a run may wrap from the end back to the start?
- How would you answer this for many range queries with point updates, using a segment tree that stores each segment's total, best prefix, best suffix and best run?
- How would you handle the extra rule that the run must contain at least k elements?
Where candidates slip
The mistakes this problem punishes.
The usual slip is starting the best answer at 0. An all-negative array then returns 0, a total that no non-empty run can reach.
- Returning the running sum instead of the best seen so far, which loses a good run as soon as a later negative value shortens it.
- Updating best before updating the running sum, so best lags one element behind.
- Writing the double loop and then being unable to say which work it repeats.
- Confusing it with the maximum product subarray, where a negative value can turn the smallest product into the largest and two values must be tracked.
- Treating the problem as "sum the positives", which ignores that the run has to be contiguous.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.