Maximum Subarray Problem
Difficulty: Medium
Category: Dynamic Programming
Problem Statement
Given an integer array nums
, find the contiguous subarray with the largest sum and return its sum.
Examples
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 <= 10^5
-10^4 <= nums[i] <= 10^4
Approach 1: Kadane's Algorithm (Optimal Solution)
Concept:
Kadane’s algorithm efficiently finds the maximum sum subarray in O(n) time by tracking:
currentSum
– the maximum sum ending at the current index.maxSum
– the maximum sum encountered so far.
Steps:
- Traverse the array.
- At each step, decide whether to:
- Continue the current subarray by adding
nums[i]
. - Start a new subarray with
nums[i]
.
- Continue the current subarray by adding
- Update
maxSum
to keep track of the highest sum encountered.
Key Formula:
currentSum = max(nums[i], currentSum + nums[i])
maxSum = max(maxSum, currentSum)
Implementation (Kadane’s Algorithm):
public class Solution {
public int MaxSubArray(int[] nums) {
int currentSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.Length; i++) {
currentSum = Math.Max(nums[i], currentSum + nums[i]);
maxSum = Math.Max(maxSum, currentSum);
}
return maxSum;
}
}
Time and Space Complexity:
- Time Complexity:
O(n)
, as we traverse the array once. - Space Complexity:
O(1)
, using only a few variables.
Approach 2: Divide and Conquer
Concept:
The Divide and Conquer approach splits the array into two halves recursively and combines results to find the maximum subarray sum.
Steps:
- Divide the array into two halves.
- Recursively find the maximum subarray sum for the left and right halves.
- Compute the maximum subarray sum that spans across the middle.
- The maximum subarray sum is the highest of:
- The left subarray sum.
- The right subarray sum.
- The sum spanning across the middle.
Implementation (Divide and Conquer):
public class Solution {
public int MaxSubArray(int[] nums) {
return MaxSubArrayDivideAndConquer(nums, 0, nums.Length - 1);
}
private int MaxSubArrayDivideAndConquer(int[] nums, int left, int right) {
if (left == right) return nums[left];
int mid = left + (right - left) / 2;
int leftMax = MaxSubArrayDivideAndConquer(nums, left, mid);
int rightMax = MaxSubArrayDivideAndConquer(nums, mid + 1, right);
int crossMax = MaxCrossingSubArray(nums, left, mid, right);
return Math.Max(Math.Max(leftMax, rightMax), crossMax);
}
private int MaxCrossingSubArray(int[] nums, int left, int mid, int right) {
int leftSum = int.MinValue, sum = 0;
for (int i = mid; i >= left; i--) {
sum += nums[i];
leftSum = Math.Max(leftSum, sum);
}
int rightSum = int.MinValue;
sum = 0;
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
rightSum = Math.Max(rightSum, sum);
}
return leftSum + rightSum;
}
}
Time and Space Complexity:
- Time Complexity:
O(n log n)
, due to recursive splitting and merging. - Space Complexity:
O(log n)
, for recursion stack.
Comparison: Kadane’s Algorithm vs. Divide and Conquer
Aspect | Kadane’s Algorithm | Divide and Conquer |
---|---|---|
Time Complexity | O(n) |
O(n log n) |
Space Complexity | O(1) |
O(log n) |
Approach | Iterative | Recursive |
Best for | Performance | Teaching recursion |
Final Thoughts:
Kadane’s algorithm is the best choice for competitive programming due to its simplicity and efficiency. The Divide and Conquer approach, while useful for understanding recursion, is not optimal for large inputs due to its higher time complexity.