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.
Problem Overview: Given an integer array nums, find the contiguous subarray with the largest possible sum and return that sum. The subarray must contain at least one element, so the solution must correctly handle cases where all numbers are negative.
The problem appears simple but tests your ability to reason about running sums and optimal substructure. It is commonly used to evaluate understanding of dynamic programming and linear-time array processing.
Approach 1: Kadane's Algorithm (O(n) time, O(1) space)
Kadane's Algorithm scans the array once while maintaining two values: the current subarray sum and the best sum seen so far. At each index, decide whether to extend the existing subarray or start a new one from the current element. This decision is made by computing current = max(nums[i], current + nums[i]). If adding the current number improves the running sum, continue the subarray; otherwise reset the sum starting at that element.
The key insight is that a negative running sum will only hurt future totals, so it should be discarded. While iterating through the array, update the global maximum whenever the current sum becomes larger. This approach runs in O(n) time because each element is processed once, and it uses O(1) space since only a few variables are maintained. Kadane's algorithm is the standard optimal solution used in interviews.
Approach 2: Divide and Conquer (O(n log n) time, O(log n) space)
The divide and conquer method splits the array into two halves and recursively finds the maximum subarray in the left half, the right half, and the subarray that crosses the midpoint. The cross-subarray is computed by expanding from the middle outward, calculating the best suffix sum on the left and the best prefix sum on the right.
The maximum of these three values becomes the answer for the current segment. The recursion continues until single-element arrays are reached. Because each level of recursion processes the full range to compute the crossing sum and there are log n levels, the total complexity becomes O(n log n) with O(log n) recursion stack space.
This approach demonstrates classic divide and conquer reasoning and is useful when discussing algorithm design patterns, but it is slower than Kadane's algorithm for this problem.
Recommended for interviews: Kadane's Algorithm is the expected solution. It shows you recognize the dynamic programming structure where the best subarray ending at index i depends on the best subarray ending at i-1. Interviewers often accept the divide-and-conquer approach as a stepping stone, but the linear-time solution demonstrates stronger algorithmic insight.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n)
Space Complexity: O(log n) for the recursion stack
| 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 |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Kadane's Algorithm | O(n) | O(1) | Best general solution. Expected approach in coding interviews. |
| Divide and Conquer | O(n log n) | O(log n) | Useful to demonstrate divide-and-conquer reasoning or recursion patterns. |
Kadane's Algorithm to Maximum Sum Subarray Problem • CS Dojo • 745,717 views views
Watch 9 more video solutions →Practice Maximum Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor