Maximum Subarray
Find the contiguous run of numbers with the largest sum. The problem that introduces Kadane's algorithm and the extend-or-restart decision. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an integer array nums. Find the contiguous, non-empty subarray with the largest sum, and return that sum.
The subarray must contain at least one element, so if every number is negative, the answer is the largest single number.
Example 1
- Input
- nums = [3, -4, 5, -1, 2, -6, 1]
- Output
- 6
The run [5, -1, 2] sums to 6.
Example 2
- Input
- nums = [-7, -3, -9]
- Output
- -3
Every option is negative, so the best is the single element -3.
Example 3
- Input
- nums = [4, -1, 4]
- Output
- 7
Taking the -1 is worth it to join the two 4s.
Constraints
- 1 ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Maximum Subarray in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Maximum Subarray
Pattern: Kadane's algorithm
Look at the best subarray that ends at index i. It either extends the best subarray ending at i - 1, or it starts fresh at i. It should start fresh exactly when the run ending at i - 1 has a negative sum, because a negative prefix only drags nums[i] down.
So one pass is enough: keep current, the best sum ending at the current index, and update it with current = max(nums[i], current + nums[i]). The answer is the largest current you ever see.
The pattern to spot is "best contiguous something": define the best answer that ends exactly here, and write it in terms of the one that ends just before.
Approach 1: Brute force with running sums
For each start index, extend the end one step at a time, keeping a running sum and the best total seen. Avoids recomputing sums from scratch, but still checks every pair of endpoints.
Time O(n²) · Space O(1)
Approach 2: Divide and conquer
Split the array in half. The best subarray lies entirely in the left half, entirely in the right half, or crosses the middle; the crossing case is the best suffix of the left plus the best prefix of the right. Recurse on both halves. A nice exercise, and it parallelizes, but it is slower than a single pass.
Time O(n log n) · Space O(log n)
Approach 3: Kadane's algorithm
Start current and best at nums[0]. For each later element x:
current = max(x, current + x): either extend the run or restart atx.best = max(best, current).
Starting from nums[0] instead of 0 is what makes the all-negative case return the largest element rather than 0.
Time O(n) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Brute force with running sums | O(n²) | O(1) |
| Divide and conquer | O(n log n) | O(log n) |
| Kadane's algorithm | O(n) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Maximum Subarray solution in Python
def max_sub_array(nums: list[int]) -> int:
current = best = nums[0]
for x in nums[1:]:
current = max(x, current + x)
best = max(best, current)
return bestMaximum Subarray solution in JavaScript
function maxSubArray(nums) {
let current = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
}Common mistakes
- Initializing `best` to 0, which returns 0 for an all-negative array even though the subarray must be non-empty.
- Resetting `current` to 0 whenever it goes negative and then updating `best` before adding the next element, which can report an empty subarray.
- Treating the problem as "sum of all positive numbers", which ignores that the subarray must be contiguous.
- Forgetting that a negative element in the middle is still worth taking when the parts on both sides outweigh it, as in `[4, -1, 4]`.
What interviewers look for
Interviewers want to hear the recurrence in words: "the best sum ending here is either this element alone or this element plus the best sum ending at the previous index." That sentence shows you understand why Kadane's works rather than just remembering the code.
Call out the all-negative case before you start coding, and show that your initialization handles it. If you have time, mention that this is a one-dimensional DP where you only keep the previous state.
Follow-up questions
How would you return the start and end indices of the subarray?
Track a tentative start that resets to `i` whenever you restart the run. Each time `best` improves, record that start and `i` as the answer.
What if the array is circular, so a subarray can wrap around the end?
The answer is the larger of the normal maximum subarray and `total - minimum subarray`, since a wrapping run is everything except a contiguous middle section. If every number is negative, return the normal maximum, because the second formula would describe an empty subarray.
What about the maximum product subarray?
Track both the largest and the smallest product ending at each index, since multiplying by a negative number turns the smallest into the largest. Update both from `x`, `maxSoFar * x`, and `minSoFar * x` at every step.
Companies that ask Maximum Subarray
Maximum Subarray is tagged by 149 companies in our interview dataset. The score shows how often it comes up at each company.
- Knowbe4100%
- Ticketmaster100%
- Mural100%
- Upstart100%
- Tech Mahindra100%
- Etched97%
- Ansys95%
- Thumbtack90%
- Target88.2%
- Dynatrace88%
- Wixcom87.3%
- Coforge86%
- Salsify86%
- Ellucian84%
- Rally Health83%
- Myriad Genetics83%
- Gartner83%
- Surveymonkey82%
- Tekion81.7%
- Infosys81.1%
- Chamberlain Group81%
- LinkedIn80.4%
- Squarepoint Capital79.4%
- Lexisnexis79%
and 125 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required