Maximum Subarray
Problem
Given an integer array nums, return the largest sum of a contiguous subarray.
- 1 ≤ nums.length ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
Example
nums = [-2,1,-3,4,-1,2,1,-5,4]6The brute-force approach would check all possible subarrays and compute their sums, which is O(n²) and inefficient. The optimal solution uses a linear scan to track the maximum subarray sum ending at each position. Starting with current_sum = 0 and max_sum = nums[0], the algorithm iterates through nums, resetting current_sum to 0 whenever it becomes negative, then adds the current number. The max_sum is updated whenever current_sum exceeds it. For the example, the maximum subarray is [4,-1,2,1] with sum 6.
Approach
Straightforward Solution
A brute-force approach enumerates all subarrays and sums them, resulting in O(n²) time complexity, which is too slow for large inputs.
Core Observation
The maximum subarray sum ending at position i depends only on the maximum subarray sum ending at position i-1 and the current element nums[i]. If the previous sum is negative, it cannot contribute positively to the current sum, so it should be reset.
Path to Optimal
The key insight is to realize that if the running sum becomes negative, it should be discarded because continuing with a negative sum only decreases the total. This leads to a linear scan where the current sum is reset to zero if it drops below zero, and the maximum sum is updated accordingly.
Optimal Approach
Iterate through the array once, maintaining a current_sum that resets to zero if negative, and a max_sum that tracks the highest sum seen so far. This approach guarantees O(n) time and O(1) space complexity.
Time
O(n)
The algorithm makes a single pass through the array, performing constant time operations per element.
Space
O(1)
Only a fixed number of variables are used to track sums, regardless of input size.
Pattern Spotlight
Dynamic Programming (Kadane's Algorithm)
The maximum subarray ending at position i either extends the maximum subarray ending at i-1 if that sum is positive, or starts fresh at i if the previous sum is negative or zero.
Solution
| 1 | class Solution:
|
| 2 | def maxSubArray(self, nums: list[int]) -> int:
|
| 3 | max_sum = nums[0]
|
| 4 | current_sum = 0
|
| 5 |
|
| 6 | for n in nums:
|
| 7 | if current_sum < 0:
|
| 8 | current_sum = 0
|
| 9 | current_sum += n
|
| 10 | max_sum = max(max_sum, current_sum)
|
| 11 |
|
| 12 | return max_sum |
Step-by-Step Solution
Initialize Maximum and Current Subarray Sums
| 3 | max_sum = nums[0]
|
| 4 | current_sum = 0
|
Objective
To set up variables that track the maximum subarray sum found so far and the current running sum.
Key Insight
Initializing max_sum to the first element ensures that the algorithm correctly handles arrays with all negative numbers. Starting current_sum at zero allows the algorithm to accumulate sums and reset when negative.
Interview Quick-Check
Core Logic
max_sum starts as nums[0] to handle edge cases where all numbers are negative.
Common Pitfalls & Bugs
Initializing max_sum to zero instead of nums[0] can cause incorrect results when all elements are negative.
Iterate Through Array to Update Running and Maximum Sums
| 6 | for n in nums:
|
| 7 | if current_sum < 0:
|
| 8 | current_sum = 0
|
| 9 | current_sum += n
|
| 10 | max_sum = max(max_sum, current_sum)
|
Objective
To scan through nums, accumulating sums and resetting when the running sum becomes negative, while tracking the maximum sum encountered.
Key Insight
Resetting current_sum to zero when it becomes negative discards subarrays that would reduce the total sum. Adding the current element to current_sum extends the current subarray. Updating max_sum ensures the algorithm remembers the best subarray sum found at any point.
Interview Quick-Check
Core Logic
The algorithm maintains a running sum that resets when negative, ensuring only positive contributions are accumulated.
State & Boundaries
The loop processes every element exactly once, guaranteeing O(n) time.
Common Pitfalls & Bugs
Failing to reset current_sum when negative leads to suboptimal sums and incorrect results.
Return the Maximum Subarray Sum Found
| 12 | return max_sum |
Objective
To output the largest sum of any contiguous subarray found during the iteration.
Key Insight
After processing all elements, max_sum holds the maximum subarray sum, which is the problem's required output.
Interview Quick-Check
Core Logic
Returning max_sum provides the final answer after considering all subarrays.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if current_sum < 0:Reset current_sum to zero if it is negative.
Discarding a negative current_sum prevents carrying forward a sum that would reduce the total of any future subarray, enabling optimal subarray detection.
max_sum = nums[0]Initialize max_sum to the first element of nums.
Setting max_sum to nums[0] ensures correct handling of arrays with all negative numbers, as it represents the best sum found so far.
current_sum += nUpdate max_sum if current_sum is greater.
Tracking the maximum sum ensures the algorithm remembers the best subarray sum found at any point during iteration.
current_sum = 0Add the current number to current_sum.
Extending the current subarray by including the current element allows the algorithm to explore larger sums.
return max_sumReturn the maximum subarray sum found.
After processing all elements, max_sum holds the largest sum of any contiguous subarray, which is the problem's solution.
current_sum = 0Initialize current_sum to zero to start accumulating sums.
Starting current_sum at zero allows the algorithm to build sums incrementally and reset when necessary.
for n in nums:Begin iterating through each number in nums.
This loop processes every element to evaluate all possible subarrays in a single pass.
Test Your Understanding
Why reset the current sum to zero when it becomes negative?
Because a negative current sum would only decrease the sum of any future subarray, so it's better to start fresh from the next element.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Maximum Subarray from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Maximum Subarray drill