Blind 75 - problem 5 : Maximum Subarray

Problem Statement

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

---

Optimal Approach

The optimal solution to this problem is Kadane’s Algorithm. This algorithm efficiently finds the maximum sum subarray in O(n) time, where n is the number of elements in the array. The basic idea is to iterate through the array while maintaining two values:

• currentSum: The maximum sum that ends at the current index.
• maxSum: The maximum sum encountered so far.

As we iterate through the array, we decide whether to add the current element to the existing subarray (currentSum + nums[i]), or to start a new subarray at the current element (nums[i]). This decision is made based on which option gives a larger sum.

---

LeetCode-Compatible Code Implementations

C++ Solution (Kadane’s Algorithm)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0]; // Initialize with the first element
        int currentSum = nums[0]; // Current subarray sum
        
        // Iterate through the array from the second element
        for (int i = 1; i < nums.size(); i++) {
            currentSum = max(nums[i], currentSum + nums[i]); // Max of current element or adding to current subarray
            maxSum = max(maxSum, currentSum); // Update maxSum
        }
        
        return maxSum;
    }
};

Regular C++ Solution with Use Cases

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0]; // Initialize with the first element
    int currentSum = nums[0]; // Current subarray sum
    
    // Iterate through the array from the second element
    for (int i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]); // Max of current element or adding to current subarray
        maxSum = max(maxSum, currentSum); // Update maxSum
    }
    
    return maxSum;
}

int main() {
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    cout << "Maximum Subarray Sum: " << maxSubArray(nums) << endl;
    return 0;
}

---

Step-by-Step Explanation of Code

1. Initialization:

   • We initialize two variables: maxSum and currentSum, both set to the first element of the array. This is because the maximum subarray must contain at least one element, and this initial value serves as a base case.

2. Iteration:

   • Starting from the second element, we iterate through the array and update currentSum at each step. We choose the larger of two options:
     • The current element nums[i] alone (starting a new subarray).
     • The sum of currentSum + nums[i] (extending the current subarray).
   • After updating currentSum, we also update maxSum, which keeps track of the maximum sum encountered so far.

3. Final Output:

   • After iterating through the array, maxSum contains the largest sum of any contiguous subarray.

---

Dry Run / Execution Steps

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

1. Initialization:

   • maxSum = -2
   • currentSum = -2

2. Iteration:

   • i = 1: currentSum = max(1, -2 + 1) = 1, maxSum = max(-2, 1) = 1
   • i = 2: currentSum = max(-3, 1 + -3) = -2, maxSum = max(1, -2) = 1
   • i = 3: currentSum = max(4, -2 + 4) = 4, maxSum = max(1, 4) = 4
   • i = 4: currentSum = max(-1, 4 + -1) = 3, maxSum = max(4, 3) = 4
   • i = 5: currentSum = max(2, 3 + 2) = 5, maxSum = max(4, 5) = 5
   • i = 6: currentSum = max(1, 5 + 1) = 6, maxSum = max(5, 6) = 6
   • i = 7: currentSum = max(-5, 6 + -5) = 1, maxSum = max(6, 1) = 6
   • i = 8: currentSum = max(4, 1 + 4) = 5, maxSum = max(6, 5) = 6

Output: 6

---

Alternative Approaches & Why Not?

1. Brute Force Approach

• Description: Check all possible subarrays and compute their sums.
• Time Complexity: O(n^2) due to nested loops.
• Space Complexity: O(1).

Why Not?: This approach is inefficient for large arrays because of its O(n^2) time complexity.

2. Sorting

• Description: Sort the array and then compute subarrays.
• Time Complexity: O(n log n) due to the sorting step.
• Space Complexity: O(1).

Why Not?: Sorting destroys the order of elements, making it difficult to find contiguous subarrays. This approach is not suitable for the problem.

---

Best Solution & Why It’s Best

Kadane's Algorithm

• Time Complexity: O(n), where n is the number of elements in the array. We only need to iterate through the array once.
• Space Complexity: O(1), as we only use a few variables to track the results.

Kadane’s Algorithm is the best solution because it is both time-efficient (linear time) and space-efficient (constant space), and it provides the correct result for the problem without needing additional space or complex operations.

Comparison Table:

Approach	Time Complexity	Space Complexity
Brute Force	O(n^2)	O(1)
Sorting	O(n log n)	O(1)
Kadane’s (Best)	O(n)	O(1)

---

Complexity Analysis

• Brute Force:

  • Time Complexity: O(n^2) because of the nested loops.
  • Space Complexity: O(1).

• Sorting:

  • Time Complexity: O(n log n) due to the sorting step.
  • Space Complexity: O(1).

• Kadane's Algorithm:

  • Time Complexity: O(n) for a single pass through the array.
  • Space Complexity: O(1).

---

Conclusion

Kadane’s Algorithm is the most efficient and optimal approach for solving the "Maximum Subarray" problem. It provides a time complexity of O(n) and a space complexity of O(1), making it the best solution for large arrays.

For similar problems, you can practice with the following:

• LeetCode - Best Time to Buy and Sell Stock.
• LeetCode - House Robber.