Maximum Subarray
Maintained by Vikas D, software engineer
You are handed an array of integers that may mix positive and negative values. A subarray is any block of consecutive elements taken from the array without skipping or reordering. Your job is to look across every possible block and report the single highest total any of them can reach.
The block must contain at least one element, so you can never return an empty selection. When every value is negative the best you can do is pick the one element closest to zero, since adding more numbers only drags the total down further.
Return just the maximum sum itself, not the indices or the block of numbers that produced it. The order of the array is fixed; you only choose where a block starts and where it ends.
Examples
The block [4, -1, 2, 1] sums to 6, which beats every other contiguous run.
Taking the whole array gives 5 + 4 - 1 + 7 + 8 = 23. The single -1 is small enough that keeping it still leaves the running total ahead.
Every value is negative, so the strongest single element wins. -1 is the least bad choice.
Constraints
- The array holds at least one element.
- Values can be negative, zero, or positive.
- The answer is the sum of one contiguous, non-empty block.
- A linear single-pass solution is expected for large inputs.
Visible test cases
- maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) == 6
- maxSubArray([1]) == 1
- maxSubArray([5,4,-1,7,8]) == 23
- maxSubArray([-3,-1,-2]) == -1
Hints
Hint 1
As you scan left to right, ask a local question at each index: is it better to extend the block ending just before me, or to start fresh at me?
Hint 2
Track a running sum for the best block that ends at the current position. If that running sum ever drops below the current element alone, throw it away and restart from the current element.
Hint 3
Keep a separate variable for the best total seen anywhere, and update it after computing each position's running sum. Seed both trackers with the first element so all-negative inputs are handled.
Approaches
Brute force over all blocks
Time O(n^2) · Space O(1)Try every start and end pair, add up the elements between them, and remember the largest sum.
- Loop the start index from 0 to the last element.
- For each start, loop an end index forward and keep a running sum of that block.
- Compare each block sum against the best seen so far and keep the larger.
- Return the best after all pairs are checked.
Optimal one pass (Kadane)
Time O(n) · Space O(1)The best block ending at each index is either that element alone or that element joined to the best block ending right before it. Carry that running value forward and watch the maximum.
- Set both the running sum and the global best to the first element.
- Walk the rest of the array. At each element set the running sum to the larger of the element by itself and the running sum plus the element.
- Update the global best with the larger of itself and the new running sum.
- Return the global best after the single pass.
Common mistakes
- Initializing the best sum to 0 breaks the all-negative case, since 0 is never a valid answer when no empty block is allowed. Seed it with the first element instead.
- Resetting the running sum to 0 rather than to the current element loses the element you are standing on when the previous run was negative.
- Confusing this with the maximum-product variant: with sums a single negative just lowers the total, but with products a negative can flip a small value into a large one, so the running-state logic is different.
- Trying to also return the block boundaries without tracking start and end indices, then misreporting them; the prompt only asks for the sum.
Follow-up variations
- Also return the start and end indices of the winning block, not just its sum.
- Handle a circular array where a block may wrap around from the end back to the front.
- Find the maximum sum when the block length is fixed at exactly k elements.
- Extend to a 2D grid and find the rectangle with the largest sum.