Leetcode 53. Maximum Subarray

 53. Maximum Subarray

Medium, Dynamic Programming

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

The Maximum Subarray problem can be solved using Kadane's Algorithm, which efficiently finds the subarray with the largest sum in $O(n)$ time complexity.

---

Approach: Kadane's Algorithm

1. Idea:

   • Use a variable currentSum to track the maximum sum of the subarray ending at the current index.
   • Use another variable maxSum to store the global maximum sum across all subarrays.

2. Steps:

   • Traverse the array.
   • At each index, decide whether to:
     • Continue the current subarray by adding the current element.
     • Start a new subarray with the current element.
   • Update maxSum to keep track of the maximum subarray sum seen so far.

3. Key Formula:

   • currentSum = Math.Max(nums[i], currentSum + nums[i])
   • maxSum = Math.Max(maxSum, currentSum)

4. Initialization:

   • currentSum starts as the first element (nums[0]).
   • maxSum also starts as nums[0].

---

Implementation:

public class Solution {
    public int MaxSubArray(int[] nums) {
        // Initialize currentSum and maxSum with the first element
        int currentSum = nums[0];
        int maxSum = nums[0];
        
        // Traverse the array starting from the second element
        for (int i = 1; i < nums.Length; i++) {
            // Update currentSum: include nums[i] in the subarray or start fresh
            currentSum = Math.Max(nums[i], currentSum + nums[i]);
            
            // Update maxSum with the maximum sum found so far
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

---

Explanation of Code:

1. Initialization:

   • currentSum starts with the first element because the subarray must include at least one element.
   • maxSum starts as the first element because it is the largest sum seen initially.

2. Iterating Through the Array:

   • For each nums[i], decide:
     • Add nums[i] to the existing subarray (currentSum + nums[i]).
     • Start a new subarray with nums[i].
   • Update maxSum to store the largest sum encountered.

3. Returning the Result:

   • The value of maxSum at the end of the loop is the largest subarray sum.

---

Complexity Analysis:

1. Time Complexity:

   • $O(n)$: The array is traversed once.

2. Space Complexity:

   • $O(1)$: Only a few variables are used.

---

Examples:

Example 1:

• Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
• Steps:
  1. Start with currentSum = -2, maxSum = -2.
  2. Update currentSum as 1, maxSum as 1.
  3. Continue until maxSum becomes 6 (subarray [4, -1, 2, 1]).
• Output: 6.

Example 2:

• Input: nums = [1]
• Output: 1.

Example 3:

• Input: nums = [5,4,-1,7,8]
• Output: 23 (subarray [5, 4, -1, 7, 8]).

This solution efficiently handles both small and large inputs, including edge cases like arrays with all negative numbers or a single element.

The Divide and Conquer approach for the Maximum Subarray problem is an alternative to Kadane's algorithm. It splits the array into two halves recursively and combines the results to find the maximum subarray sum.

---

Approach: Divide and Conquer

1. Divide:

   • Split the array into two halves at the middle index.

2. Conquer:

   • Recursively find the maximum subarray sum for the left and right halves.

3. Combine:

   • Compute the maximum subarray sum that spans across the middle of the array.

4. Final Result:

   • The maximum subarray sum for the current array is the maximum of:
     • Maximum subarray sum in the left half.
     • Maximum subarray sum in the right half.
     • Maximum subarray sum spanning the middle.

---

Implementation:

public class Solution {
    public int MaxSubArray(int[] nums) {
        return MaxSubArrayDivideAndConquer(nums, 0, nums.Length - 1);
    }

    private int MaxSubArrayDivideAndConquer(int[] nums, int left, int right) {
        // Base case: single element
        if (left == right) {
            return nums[left];
        }

        // Find the middle index
        int mid = left + (right - left) / 2;

        // Recursively find the maximum subarray sum in the left and right halves
        int leftMax = MaxSubArrayDivideAndConquer(nums, left, mid);
        int rightMax = MaxSubArrayDivideAndConquer(nums, mid + 1, right);

        // Find the maximum subarray sum that crosses the middle
        int crossMax = MaxCrossingSubArray(nums, left, mid, right);

        // Return the maximum of the three
        return Math.Max(Math.Max(leftMax, rightMax), crossMax);
    }

    private int MaxCrossingSubArray(int[] nums, int left, int mid, int right) {
        // Calculate maximum sum in the left half (including the middle element)
        int leftSum = int.MinValue, sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.Max(leftSum, sum);
        }

        // Calculate maximum sum in the right half
        int rightSum = int.MinValue;
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.Max(rightSum, sum);
        }

        // Combine the results from both halves
        return leftSum + rightSum;
    }
}

---

Explanation of Code:

1. Recursive Splitting:

   • The array is split into two halves until each segment contains only one element.

2. Base Case:

   • If left == right, the subarray contains only one element, and the result is the value of that element.

3. Crossing Subarray:

   • To compute the maximum sum across the middle, iterate:
     • From the middle to the left for the left sum.
     • From the middle to the right for the right sum.
   • Combine these sums for the cross-sum.

4. Result:

   • The result for the current segment is the maximum of:
     • The left segment sum.
     • The right segment sum.
     • The cross-segment sum.

---

Complexity Analysis:

1. Time Complexity:

   • $T(n) = 2T(n/2) + O(n)$, solving to $O(n \log n)$.
   • The recursion divides the array into two halves and processes them.

2. Space Complexity:

   • $O(\log n)$ for recursion stack.

---

Examples:

Example 1:

• Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
• Divide:
  • Left: [-2,1,-3,4], Right: [-1,2,1,-5,4]
• Combine:
  • Max left: 4, Max right: 4, Max cross: 6.
• Output: 6.

Example 2:

• Input: nums = [1]
• Base case: Return 1.

Example 3:

• Input: nums = [5,4,-1,7,8]
• Divide:
  • Left: [5,4,-1], Right: [7,8].
• Combine:
  • Max left: 8, Max right: 15, Max cross: 23.
• Output: 23.

---

Comparison with Kadane's Algorithm:

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
Preferred for	Simplicity, performance	Teaching recursion

Kadane’s algorithm is faster and simpler for competitive programming, while the Divide and Conquer approach is useful for understanding recursive problem-solving techniques.