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

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.
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.
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]`

Initialization:
- maxSum = -2
- currentSum = -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.

Sandip Mhaske

Senior Engineer • Author of 1419 guides • Follow for System Design & .NET deep-dives

About