Kadane’s Algorithm: The Key to Optimal Subarray Sum

The maximum subarray problem is all about finding a contiguous subarray with the largest sum. Basically, you need to look at an array of numbers and find the chunk that adds up to the biggest total. For example, if you have the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray with the largest sum is [4, -1, 2, 1], which adds up to 6.

The brute force solution involves creating two pointers and incrementing one while keeping the other constant. You calculate the sum and keep checking for the maximum sum. Once the inner pointer is exhausted, you increment the outer pointer and repeat the same process. Here's the pseudo code:

for(int i = 0; i < n; i++){
    int sum = 0;
    for(int j = i; j < n; j++){
        sum += arr[j]
        maxSum = max(sum, maxSum)
    }
}
return maxSum;

This solution takes O(n^2) time, which is pretty slow.

But fear not! Kadane's algorithm is here to save the day. This algorithm states that either the maximum subarray sum ending at position i+1 includes the maximum subarray sum ending at position i as a prefix, or it doesn't. Here's the solution using Kadane's algorithm:

public int maxSubArray(int[] nums) {

    int finalMaxSum = nums[0];
    int maxSumSoFar = nums[0];

    for(int i = 1; i < nums.length; i++){
        maxSumSoFar = Math.max(nums[i], nums[i] + maxSumSoFar);
        finalMaxSum = Math.max(maxSumSoFar, finalMaxSum);
    }
    return finalMaxSum;
}

This solution is much more efficient than the brute force approach and runs in O(n) time.

If you want to learn more about the maximum subarray problem, check out the Wikipedia page at https://en.wikipedia.org/wiki/Maximum_subarray_problem.