Maximum Subarray - Solution & Explanation
Problem Statement
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Approach Overview
Problem Overview: Given an integer array nums, find the contiguous subarray with the largest possible sum and return that sum. The challenge is identifying the best subarray without checking every possible range.
Approach 1: Kadane's Algorithm (O(n) time, O(1) space)
Kadane's Algorithm scans the array once while maintaining the maximum sum ending at the current position. At each index, you decide whether to extend the previous subarray (current_sum + nums[i]) or start a new subarray at the current element. This works because any negative running sum only hurts future results, so resetting when the sum becomes smaller than the current element keeps the best candidate alive. You track a global maximum while iterating. The algorithm uses only two variables and runs in linear time, making it the most efficient and commonly expected solution for this problem.
The idea closely relates to dynamic programming. Each state represents the best subarray ending at index i, computed from the state at i-1. Because the recurrence depends only on the previous value, the DP table compresses into constant space.
Approach 2: Divide and Conquer (O(n log n) time, O(log n) space)
The divide and conquer strategy splits the array into two halves recursively. For each segment, compute three values: the best subarray entirely in the left half, the best entirely in the right half, and the best crossing the midpoint. The crossing sum is calculated by expanding from the midpoint outward to capture the maximum suffix of the left side and maximum prefix of the right side. The final answer for that segment is the maximum of these three candidates.
This method demonstrates how the problem can be broken into independent subproblems, a common pattern in divide and conquer algorithms. Although slower than Kadane's algorithm due to recursive splitting and merging, it helps build intuition about how subarray boundaries interact across partitions. The recursion depth contributes O(log n) auxiliary space.
Both approaches operate on a simple array structure and rely on tracking partial sums rather than enumerating all subarrays.
Recommended for interviews: Kadane's Algorithm is the expected answer. Interviewers want to see that you recognize the linear-time dynamic programming pattern and can derive the recurrence max(nums[i], current_sum + nums[i]). Mentioning the divide and conquer solution shows deeper understanding of the problem structure, but implementing Kadane's algorithm cleanly demonstrates strong algorithmic intuition and optimal complexity.
Approach 1: Approach 1: Kadane's Algorithm
This approach uses Kadane's Algorithm, which is an efficient way to find the maximum subarray sum in linear time.
We iterate through the array, keeping track of the maximum sum of the subarray ending at the current position and the overall maximum sum found so far.
The algorithm maintains two variables: current_max, which is the maximum sum of the subarray that ends at the current index, and global_max, which is the maximum sum found so far.
This C code implements Kadane's Algorithm. We initialize current_max and global_max to the first element of the array, then iterate through the array, updating these values based on the logic of Kadane's algorithm.
Complexity
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), because we are using a constant amount of extra space.
Approach 2: Approach 2: Divide and Conquer
This approach splits the array into two halves and finds the maximum subarray sum for each half recursively. It also considers the possibility of the maximum subarray crossing the midpoint.
To find the maximum crossing subarray, we begin at the midpoint and expand outward to the left and right, keeping track of the maximum sum.
This approach effectively divides the problem into smaller subproblems and conquers each independently, then combines their results.
This C implementation uses divide and conquer to find the maximum contiguous subarray sum. It divides the array into two halves, recursively finds the maximum subarray sum in each half, and also finds the maximum crossing sum that can be obtained by including elements from both halves.
Complexity
Time Complexity: O(n log n)
Space Complexity: O(log n) for the recursion stack
Approach 3: Dynamic Programming
We define f[i] to represent the maximum sum of a contiguous subarray ending at element nums[i]. Initially, f[0] = nums[0]. The final answer we seek is max_{0 leq i < n} f[i].
Consider f[i] for i geq 1. Its state transition equation is:
$
f[i] = max(f[i - 1] + nums[i], nums[i])
That is:
f[i] = max(f[i - 1], 0) + nums[i]
Since f[i] is only related to f[i - 1], we can use a single variable f to maintain the current value of f[i] and perform the state transition. The answer is max_{0 leq i < n} f.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Approach 4: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Kadane's Algorithm | Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(1), because we are using a constant amount of extra space. |
| Approach 2: Divide and Conquer | Time Complexity: O(n log n) Space Complexity: O(log n) for the recursion stack |
| Dynamic Programming | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Kadane's Algorithm | O(n) | O(1) | Best general solution. Preferred in interviews and production due to linear time and constant space. |
| Divide and Conquer | O(n log n) | O(log n) | Useful for understanding subarray boundaries and recursive problem decomposition. |
Video Solution
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 745,750 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Subarray easy or hard?
How to solve Maximum Subarray in O(n)?
What is the best approach for Maximum Subarray?
What data structure is used in Maximum Subarray?
What is the time complexity of Maximum Subarray?
Maximum Subarray Python or Java solution approach?
Is Maximum Subarray asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Maximum Subarray with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor