Maximum Subarray
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Adobe, Atlassian, Walmart
Problem
Given an integer array nums, find the subarray with the largest sum and return its sum. This is Kadane's algorithm, one of the most elegant DP solutions.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Netflix | Medium | View all Netflix questions → |
| Adobe | Medium | View all Adobe questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
At each position, you have two choices: extend the previous subarray or start fresh here. If the previous sum is negative, starting fresh is better.
The recurrence: maxEndingHere = max(nums[i], maxEndingHere + nums[i]). Either start a new subarray at nums[i] or extend the existing one.
Track the global maximum as you go. maxSoFar = max(maxSoFar, maxEndingHere). One pass through the array.
Why it works: maxEndingHere represents the best subarray ending at the current position. If the running sum goes negative, it's never worth extending — start fresh.
Visual walkthrough for [-2,1,-3,4,-1,2,1,-5,4]:
num=-2: maxEnd=-2, maxSoFar=-2
num=1: maxEnd=max(1,-2+1)=1, maxSoFar=1
num=-3: maxEnd=max(-3,1-3)=-2, maxSoFar=1
num=4: maxEnd=max(4,-2+4)=4, maxSoFar=4
num=-1: maxEnd=max(-1,4-1)=3, maxSoFar=4
num=2: maxEnd=max(2,3+2)=5, maxSoFar=5
num=1: maxEnd=max(1,5+1)=6, maxSoFar=6
num=-5: maxEnd=max(-5,6-5)=1, maxSoFar=6
num=4: maxEnd=max(4,1+4)=5, maxSoFar=6
Result: 6 (subarray [4,-1,2,1])
Edge cases: all negative numbers (return the largest single element), single element (return it).
Optimal Approach
Kadane's algorithm:
Step 1: Initialize maxEndingHere = nums[0], maxSoFar = nums[0].
Step 2: For each num in nums[1:]:
maxEndingHere = max(num, maxEndingHere + num)
maxSoFar = max(maxSoFar, maxEndingHere)
Step 3: Return maxSoFar.
The key insight: if maxEndingHere becomes negative, it's better to start fresh at the next element. A negative running sum can only hurt the next subarray.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Confusing "maximum subarray" with "maximum element." The subarray must be contiguous, and you're looking for the maximum sum, not the maximum single element.
Not handling all-negative arrays. If all elements are negative, the answer is the largest (least negative) single element, not 0.
Trying to use a separate array for dp. Kadane's algorithm can be done in O(1) space with just two variables.
Forgetting to initialize the result. Set result = nums[0] (or negative infinity), not 0. If all elements are negative, 0 would be wrong.
Thinking the subarray must start at index 0. Kadane's allows the maximum subarray to start anywhere — it tracks the best ending at each position and the global best across all positions.
Solution Code
def maxSubArray(nums):
max_ending_here = max_so_far = nums[0]
for num in nums[1:]:
max_ending_here = max(num, max_ending_here + num)
max_so_far = max(max_so_far, max_ending_here)
return max_so_farFrequently Asked Questions
What is the Maximum Subarray problem?
Given an integer array nums, find the subarray with the largest sum and return its sum. This is Kadane's algorithm, one of the most elegant DP solutions.
How do you solve Maximum Subarray?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Subarray?
Maximum Subarray is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Adobe, Atlassian, Walmart. It is a medium difficulty problem.
What are common mistakes on Maximum Subarray?
- Confusing "maximum subarray" with "maximum element." The subarray must be contiguous, and you're looking for the maximum sum, not the maximum single element.
- Not handling all-negative arrays. If all elements are negative, the answer is the largest (least negative) single element, not 0.
- Trying to use a separate array for dp. Kadane's algorithm can be done in `O(1)` space with just two variables.
- Forgetting to initialize the result. Set result = `nums[0]` (or negative infinity), not 0. If all elements are negative, 0 would be wrong.
- Thinking the subarray must start at index 0. Kadane's allows the maximum subarray to start anywhere — it tracks the best ending at each position and the global best across all positions.