53. Maximum Subarray

Intitution

The key idea is to maintain a running sum of the subarray and reset it whenever it becomes negative. A negative sum will only reduce the total of future subarrays, so we discard it and start fresh. We also keep track of the maximum sum seen so far while iterating.

Kadane’s Algorithm works by:

1. Tracking a running sum (currentSum).

2. Resetting the running sum to 0 whenever it drops below 0.

3. Keeping track of the maximum sum seen so far (maxSum).

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(n)$

Code

public int maxSubArray(int[] nums) {

    // currentSum stores the sum of the current subarray
    int currentSum = 0;
    
    // maxSum keeps track of the maximum subarray sum found so far
    int maxSum = Integer.MIN_VALUE;

    // Iterate through all elements of the array
    for (int i = 0; i < nums.length; ++i) {

        // Add current number to the running sum
        currentSum += nums[i];

        // Update maxSum if currentSum is greater
        maxSum = Math.max(currentSum, maxSum);

        // If running sum is negative, reset it to 0
        if (currentSum < 0) currentSum = 0;
    }

    // Return the maximum subarray sum found
    return maxSum;
}