Maximum Subarray (Kadane's Algorithm) - Leetcode 53

Problem Statement

Problem Link

Given an integer array nums, find the subarray with the largest sum, and returnits 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.

Solution

I. Brute force approach O(n^2)

The straightforward approach to finding the maximum subarray sum is to calculate the sum of all possible subarrays. This can be achieved using two nested for loops that iterate through all possible pairs of indices (i, j), where i < j. Store the current maximum sum value after each subarray.

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        for(int i=0; i<nums.length; i++) {
            int subSum = 0;
            for(int j=i; j<nums.length; j++){
                subSum+=nums[j];
                ans = Math.max(ans,subSum);
            }
        }
        return ans;
    }
}

II. Optimal Approach O(n)

We will use the accumulator strategy. An accumulator is generally employed to calculate the sum of all the elements in an array. If we delve into the process of calculating the sum of the array, we will discover that the accumulator holds the sum up to a particular index. Therefore, in this case, the subarray sum equals the total array sum.

//arr = [5, -3, -1, 4, 8, 3]
//acc->  5,  2,  1, 5, 13, 16
//Accumulator
for(int i=0; i<arr.length; i++){
    acc+=arr[i];
}

Now, we will modify the accumulator according to our needs. The accumulator will keep accumulating values as long as it is increasing, and this value should be greater than the current index value. The reason is that if the current index value, nums[i], is higher than the sum of acc + nums[i], then it indicates that nums[i] will be the maximum subarray sum value, and the new accumulator sum value should start with nums[i]. The accumulator will aim to maintain subarray sum values that have the potential for the maximum subarray sum value.

class Solution {
    public int maxSubArray(int[] nums) {
        int acc = nums[0];
        int ans = nums[0];

        for(int i=1; i<nums.length; i++) {
            if(acc+nums[i]>nums[i]) {
                acc+=nums[i];
            } else{
                acc = nums[i];
            }
            ans = Math.max(ans,acc);
            // System.out.println(ans+" "+ acc);
        }
        return ans;
    }
}

III. Optimal Approach (Easy)

The fundamental concept is to eliminate subarrays with negative sums, as their inclusion would decrease the overall sum. If the sum is negative, we set it to default to 0 during the process. Setting it to 0 does not impact our final result, as we subsequently add the element and compare it with the global maximum.

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int ans = nums[0];
        for(int i=0; i<nums.length; i++){
            sum+=nums[i];
            ans = Math.max(ans, sum);
            if(sum<0){
                sum=0;
            }
        }
        return ans;
    }
}