Watch 10 video solutions for Maximum Subarray, a medium level problem involving Array, Divide and Conquer, Dynamic Programming. This walkthrough by CS Dojo has 745,717 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |