53. Maximum Subarray

Description

The task is to find the maximum sum of a contiguous subarray within a given integer array. This problem is a classic example of using dynamic programming or a greedy approach to solve the maximum subarray sum efficiently.

Intuition

To solve this problem, we need to track the maximum sum of subarrays as we iterate through the array. The idea is to maintain a running sum of the current subarray and update the maximum sum whenever this running sum exceeds the previously recorded maximum. If the running sum drops below zero, we reset it to zero, since a negative running sum would not contribute positively to any future subarray.

Approach

1. Initialization: - Start by initializing max_sum to a very small value (negative infinity) to ensure any subarray sum will be greater. - Use current_sum to keep track of the sum of the current subarray.
2. Iteration: - Loop through each element in the array, adding the element to current_sum. - Update max_sum if current_sum is greater than the current max_sum. - If current_sum becomes negative, reset it to zero. This is because continuing with a negative sum would decrease the sum of any future subarray.
3. Result: - After processing all elements, max_sum will hold the maximum sum of any contiguous subarray.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. The algorithm processes each element once, resulting in linear time complexity.

Space Complexity:

O(1), as only a fixed amount of extra space is used regardless of the input size. The algorithm uses a few variables to keep track of the current sum and maximum sum, but does not require additional space proportional to the input size.

Code

C++

class Solution {
public:
    int maxSubArray(vector& nums) {
        int max = INT_MIN;
        int subArr = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            subArr += nums[i];
            if (max < subArr) {
                max = subArr;
            }
            if (subArr < 0) {
                subArr = 0;
            }
        }
        
        return max;
    }
};

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float('-inf')  # Initialize to the smallest possible value
        current_sum = 0  # Variable to keep track of the current subarray sum
        
        for num in nums:
            current_sum += num
            if current_sum > max_sum:
                max_sum = current_sum
            if current_sum < 0:
                current_sum = 0 
        
        return max_sum 

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE; // Initialize to the smallest possible integer value
        int subArr = 0; // Variable to keep track of the current subarray sum
        
        for (int num : nums) {
            subArr += num;
            if (subArr > max) {
                max = subArr;
            }
            if (subArr < 0) {
                subArr = 0;
            }
        }
        
        return max;
    }
}

JavaScript

var maxSubArray = function (nums) {
    let max = -Infinity
    let subArr = 0
    for (let i = 0; i <= nums.length - 1; ++i) {
        subArr += nums[i]
        if (max < subArr) {
            max = subArr
        }
        if (subArr < 0) {
            subArr = 0
        }
    }
    return max
};