Kadane's Algorithm

Concept

The Maximum Subarray Problem is one of the most famous computer science problems: “Given an integer array (containing positive and negative numbers), find the contiguous subarray which has the largest sum, and return its sum.”

• Naive approach: Double for loop to check every possible subarray. $O(N^2)$ time.
• Optimal approach: Kadane’s Algorithm. $O(N)$ time, $O(1)$ space.

Kadane’s Algorithm uses a brilliant piece of dynamic programming logic: Should I add the current number to my existing running subarray, or should I throw my existing subarray in the trash and start a brand new one from scratch?

Mental Model

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

We maintain a current_sum and a max_sum. As we walk through the array:

1. Index 0 (-2): current_sum = -2. max_sum = -2.
2. Index 1 (1): Should we add 1 to -2 (making -1)? No! That drags us down. We are better off throwing away the -2 and starting a brand new subarray beginning with exactly 1.
   current_sum = Math.max(1, -2 + 1) = 1. max_sum = 1.
3. Index 2 (-3): Add it to 1. current_sum = -2.
4. Index 3 (4): Should we add 4 to our running -2 (making 2)? No! Throw away the negative baggage. Start fresh with 4.
   current_sum = 4. max_sum = 4.

The core rule of Kadane’s Algorithm: If the current running sum ever becomes negative, it is mathematically worthless. Throw it away and reset it to 0.

Implementation

// Time Complexity: O(N)
// Space Complexity: O(1)
function maxSubArray(nums: number[]): number {
    let maxSum = nums[0];
    let currentSum = 0;

    for (let num of nums) {
        // If our running sum dipped below 0, it's useless baggage. Drop it.
        if (currentSum < 0) {
            currentSum = 0;
        }
        
        currentSum += num;
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

(Note: Initializing maxSum = nums[0] instead of 0 protects against arrays that only contain negative numbers, like [-3, -5], where the correct answer is -3, not 0).

Interview Questions

Q: Can you solve the Maximum Subarray problem using a Sliding Window instead of Kadane’s Algorithm?
A: Yes, Kadane’s Algorithm is actually just a highly specific variation of the Dynamic Sliding Window technique!
In a standard Sliding Window, the Right pointer expands the window by adding numbers, and the Left pointer shrinks the window based on a condition.
In Kadane’s Algorithm, the currentSum < 0 check is effectively the condition that causes the Left pointer to instantly teleport to the Right pointer’s location, abandoning the old window and starting a new one.

Q: A variation of the problem asks you to return the actual Start and End indices of the maximum subarray, not just the sum. How do you modify Kadane’s Algorithm to do this?
A: You introduce three new variables: tempStart, bestStart, and bestEnd.
Every time you reset currentSum = 0 (throwing away the baggage), you also update tempStart = i + 1 (marking the potential start of a new subarray).
Whenever you find a new maxSum (currentSum > maxSum), you lock in the boundaries: you update bestStart = tempStart and bestEnd = i. At the end of the loop, bestStart and bestEnd will hold the exact indices of the winning subarray.