Kadane's Algorithm: Maximum Subarray Sum

1. The Problem: Maximum Subarray Sum

First, let's clearly define the problem. Given an array of integers (which can be positive, negative, or zero), we need to find the contiguous subarray that has the largest sum and return that sum.

For example, in the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the subarray [4, -1, 2, 1] has the largest sum, which is 6.

A straightforward, brute-force approach would be to generate every possible subarray, calculate its sum, and keep track of the maximum sum found. This would involve nested loops, resulting in an O(n²) time complexity. While this works, interviewers will almost certainly ask for a more optimal solution.

2. The Intuition Behind Kadane's Algorithm

Kadane's algorithm is brilliant because it solves this in a single pass. The core idea is to iterate through the array and, at each position, make a simple decision:

Should I extend the current subarray by adding the new element, or should I discard the old subarray and start a new one with just the current element?

Let's maintain two variables:

1. currentSum: The maximum sum of a subarray ending at the current position.
2. maxSum: The overall maximum sum found so far, across the entire array.

As we iterate through the array, for each element num, we update currentSum by choosing the maximum of two options:

• num: Start a new subarray here. This is a good choice if the currentSum up to the previous element was negative, as carrying a negative sum forward will only decrease our total.
• currentSum + num: Extend the existing subarray. This is a good choice if the currentSum is positive and worth carrying forward.

This logic is perfectly captured in this simple line:
currentSum = Math.max(num, currentSum + num);

After updating currentSum, we then check if this new currentSum is greater than our overall maxSum and update maxSum if necessary.

The following video from the "take U forward" channel provides an excellent visual walkthrough of this logic. Pay attention to how the sum is reset whenever it becomes disadvantageous to carry it forward.

Here is a static visualization that walks through an example step-by-step.

3. Java Implementation and Edge Cases

Let's translate this logic into clean Java code. A crucial detail is how we initialize our variables. To correctly handle arrays that contain only negative numbers, we should initialize both currentSum and maxSum to the first element of the array, not to 0.

Here is a complete Java implementation based on that logic:

public class KadanesAlgorithm {

    public static int maxSubArraySum(int[] nums) {
        // Handle empty or null array
        if (nums == null || nums.length == 0) {
            // Or throw an exception, depending on requirements
            return 0; 
        }

        int maxSum = nums[0];
        int currentSum = nums[0];

        // Start loop from the second element
        for (int i = 1; i < nums.length; i++) {
            // Decision: Extend the previous subarray or start a new one?
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            
            // Update the overall maximum sum if the current one is better
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("The maximum subarray sum is: " + maxSubArraySum(arr)); // Output: 6
        
        int[] allNegative = {-5, -1, -3};
        System.out.println("The maximum subarray sum is: " + maxSubArraySum(allNegative)); // Output: -1
    }
}

Complexity Analysis:

• Time Complexity: O(n), because we iterate through the array exactly once.
• Space Complexity: O(1), because we only use a few variables to store our sums, regardless of the input array's size.

4. Follow-up: Printing the Subarray

A common follow-up question in interviews is to not only return the maximum sum, but also the subarray itself. We can extend Kadane's algorithm to keep track of the start and end indices of the maximum subarray found so far.

The logic is as follows:

1. Maintain a start and end index for the final answer.
2. Maintain a tempStart index that marks the beginning of the current subarray we are considering.
3. When we decide to start a new subarray (i.e., currentSum is reset to nums[i]), we update tempStart to the current index i.
4. Whenever we update our overall maxSum, we also update our final start and end indices using tempStart and the current index i.

Here's the Java code for the extended algorithm:

import java.util.Arrays;

public class KadanesAlgorithmPrintSubarray {

    public static void maxSubArrayWithIndices(int[] nums) {
        if (nums == null || nums.length == 0) {
            System.out.println("Array is empty.");
            return;
        }

        int maxSum = nums[0];
        int currentSum = 0; // We can start currentSum at 0 for this variation

        int start = 0;
        int end = 0;
        int tempStart = 0;

        for (int i = 0; i < nums.length; i++) {
            currentSum += nums[i];

            if (currentSum > maxSum) {
                maxSum = currentSum;
                start = tempStart;
                end = i;
            }

            // If currentSum becomes negative, it cannot contribute positively
            // to any future subarray, so we reset it and update the temp start index.
            if (currentSum < 0) {
                currentSum = 0;
                tempStart = i + 1;
            }
        }

        System.out.println("Maximum subarray sum is: " + maxSum);
        System.out.print("The subarray is: ");
        // Note: Slicing arrays in Java is less direct than in Python.
        // We can create a copy or just print the elements.
        for (int i = start; i <= end; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
         int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
         maxSubArrayWithIndices(arr); 
         // Expected: sum = 6, subarray = 4 -1 2 1
    }
}

Conclusion

Congratulations! You've just learned one of the most elegant algorithms for array manipulation. Kadane's algorithm is a prime example of dynamic programming where an optimal solution is built up by making simple, local decisions at each step.

Key Takeaways:

• Problem: Find the contiguous subarray with the largest sum.
• Kadane's Algorithm: An O(n) time, O(1) space solution.
• Core Logic: At each element, decide whether to extend the current subarray or start a new one. This is encapsulated by currentSum = Math.max(num, currentSum + num).
• Edge Cases: Initializing maxSum and currentSum to the first element correctly handles arrays with all negative numbers.
• Interview Follow-up: The algorithm can be easily extended to track the start and end indices of the resulting subarray.

Preview of the next lesson:
We will continue our exploration of efficient array algorithms by looking at the Dutch National Flag algorithm. This is a clever method for sorting an array of elements into three distinct groups (like the three colors of the Dutch flag) in a single pass. It's a fundamental partitioning technique used in more complex sorting algorithms like Quicksort.