Kadane's Algorithm: Maximum Subarray Sum

The Maximum Subarray Sum Problem

First, let's clearly define the problem. Given an array of integers, which can include both positive and negative numbers, we need to find the contiguous subarray (a sequence of adjacent elements) that has the largest possible sum. We then return that sum.

For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the subarray [4, -1, 2, 1] has the sum 6, which is the largest sum you can get from any contiguous subarray in this array.

Following your preferred learning style, let's start with the most straightforward approach and refine it until we arrive at the optimal solution.

Approach 1: The Brute-Force Solution O(n³)

The most direct way to solve this is to consider every single possible contiguous subarray, calculate the sum of each one, and keep track of the maximum sum we've seen.

How do we generate every subarray? We can use two nested loops to define the start and end points of the subarray.

1. An outer loop (i) selects the starting index of the subarray.
2. An inner loop (j) selects the ending index of the subarray.

Once we have a subarray defined by i and j, we need a third loop (k) to iterate from i to j and calculate its sum. This three-loop structure immediately points to a cubic time complexity, O(n³).

Let's use the tutorial from "takeUforward" as our guide through this process.

While this approach works, an O(n³) solution is highly inefficient and would be too slow for typical constraints in an interview or on a competitive programming platform.

Approach 2: A Better Solution O(n²)

We can make a simple but significant optimization. In the O(n³) approach, we repeatedly recalculated the sum of subarrays. Notice that when we extend a subarray [i...j] to [i...j+1], the new sum is just the old sum plus the new element array[j+1].

This insight allows us to eliminate the third loop. We can use just two loops:

1. The outer loop (i) still selects the starting index.
2. The inner loop (j) iterates from i to the end of the array. Inside this loop, we maintain a current_sum for the subarray [i...j], updating it by adding the element at j in each step.

This reduces the time complexity to O(n²). This is an improvement, but for large arrays (e.g., n = 10^5), n² is still too slow and would likely result in a "Time Limit Exceeded" error.

The Codecademy article provides a clear explanation of this optimization step.

Now, let's make the leap to the optimal solution.

Approach 3: Optimal Solution - Kadane's Algorithm O(n)

Kadane's algorithm is a brilliant and intuitive dynamic programming approach that solves this problem in a single pass (O(n) time) and with constant extra space (O(1)).

The core idea is to iterate through the array while keeping track of two values:

1. current_sum: The maximum sum of a subarray ending at the current position.
2. max_so_far: The overall maximum sum found anywhere in the array so far.

Here's the logic:
For each element in the array, we add it to current_sum. Then, we update max_so_far if current_sum is greater.

The crucial step, and the main insight of the algorithm, is this: If current_sum ever becomes negative, we reset it to 0.

Why? A negative current_sum means the subarray ending at this point has a negative total. If we were to carry this negative sum forward, it would only decrease the sum of any future subarray. It's always better to abandon the negative-sum subarray and start a new one from the next element. Starting a new subarray is equivalent to resetting current_sum to 0 and then adding the next element.

Let's watch Striver's explanation of this intuition.

The following image provides a step-by-step visualization of the algorithm in action.

Now, let's solidify this with the formal algorithm description and Java code from our main resource.

Here is a clean Java implementation of Kadane's algorithm:

public class KadaneAlgorithm {
    public int maxSubArray(int[] nums) {
        long max_so_far = Long.MIN_VALUE; // Use long to avoid overflow, though problem constraints might not need it.
        long current_sum = 0;

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

            if (current_sum > max_so_far) {
                max_so_far = current_sum;
            }

            if (current_sum < 0) {
                current_sum = 0;
            }
        }
        
        // A special case: if all numbers are negative, max_so_far will be the largest (least negative) of them.
        // If the problem allowed an empty subarray (sum 0), you might need an extra check here.
        // For this standard version, this is sufficient.
        return (int) max_so_far;
    }
}

A quick note on an edge case: What if all the numbers in the array are negative, like [-5, -1, -3]? In this case, current_sum will be reset to 0 frequently, but max_so_far will correctly capture the largest (i.e., least negative) single element, which is -1. The implementation shown handles this correctly.

Follow-up: Printing the Subarray

A common follow-up question in interviews is to not only return the maximum sum but also print the actual subarray that produces it.

To do this, we can augment Kadane's algorithm:

• We need variables ansStart and ansEnd to store the start and end indices of the best subarray found so far.
• We also need a start variable to mark the potential beginning of a new subarray.
• When does a new potential subarray start? Right after current_sum was reset to 0. So, when current_sum is 0, we can set start = i.
• Whenever we update max_so_far, we also update ansStart = start and ansEnd = i.

The "takeUforward" resources cover this modification perfectly.

Conclusion

Today we've dissected the Maximum Subarray Sum problem, following our structured approach from a naive O(n³) solution to the beautifully simple and efficient O(n) Kadane's algorithm. This algorithm is a testament to how a clever insight can lead to a massive performance improvement.

Key Takeaways:

• Problem Progression: We saw how to refine a brute-force O(n³) solution to a better O(n²) one, and finally to the optimal O(n) solution. This thought process is exactly what interviewers look for.
• Kadane's Algorithm: A single-pass algorithm that efficiently finds the maximum subarray sum.
• The Core Insight: The key is to discard any subarray prefix that has a negative sum, as it can't contribute positively to any larger subarray. This is achieved by resetting the current_sum to 0 whenever it becomes negative.
• Interview Follow-up: You learned how to extend the basic algorithm to also return the start and end indices of the maximum sum subarray.

In our next lesson, we will dive into prefix sums. This technique allows you to answer range-sum queries (i.e., finding the sum of elements between any two indices) very efficiently, providing a different but equally powerful tool for solving array-based problems.