Maximum Subarray

Concept

LeetCode #53.
Problem: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 (The contiguous subarray [4, -1, 2, 1] adds up to 6, which is the absolute highest possible score).

Because a “Subarray” must be perfectly contiguous (elements side-by-side), we cannot just sort the array or use Backtracking.
The Brute Force approach checks every single possible subarray using nested for loops, resulting in an $O(N^2)$ or $O(N^3)$ disaster.

Kadane’s Algorithm ($O(N)$)

In 1984, a professor named Jay Kadane invented an elegant $O(N)$ Dynamic Programming solution that solves this problem in a single pass.

The Philosophy:
Imagine you are walking left-to-right through the array, carrying a “Running Total” in your backpack.
Every time you step on a number, you add it to your backpack.

If your backpack total becomes Negative, it is mathematically toxic.
If you have -3 in your backpack, and you step on a 4, (-3) + 4 = 1. Your backpack dragged the 4 down to a 1!
If you had simply thrown your backpack in the trash and started fresh at the 4, your total would be 4!

The Golden Rule of Kadane:
If your running total ever drops below 0, throw it away. Reset it to 0.

Implementation

// Time Complexity: O(N) (One single pass)
// Space Complexity: O(1)

function maxSubArray(nums: number[]): number {
    // If the array only has negative numbers (e.g., [-5, -2, -9]), 
    // we MUST return the absolute largest negative number (-2). 
    // Therefore, our maxScore tracker must start at the lowest possible number,
    // NOT zero!
    let maxScore = -Infinity;
    
    let currentRunningTotal = 0;

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];

        // 1. Add the current number to our backpack
        currentRunningTotal += num;

        // 2. Did we beat the global high score?
        if (currentRunningTotal > maxScore) {
            maxScore = currentRunningTotal;
        }

        // 3. Kadane's Rule: Is our backpack mathematically toxic?
        // If our running total is negative, it will mathematically drag down 
        // the next number. We dump the backpack!
        if (currentRunningTotal < 0) {
            currentRunningTotal = 0;
        }
    }

    return maxScore;
}

The DP Conceptualization

Kadane’s Algorithm is literally just Dynamic Programming with State Reduction ($O(1)$ space).

If we built a full dp Array, the Recurrence Relation would be:
dp[i] = Math.max(nums[i], nums[i] + dp[i-1])

Translated to English: “At index i, what is the best possible score? Is it better to start a brand new sequence here (nums[i]), or is it better to attach myself to the previous sequence (nums[i] + dp[i-1])?”

If dp[i-1] is a negative number, nums[i] + (-5) will be smaller than just nums[i]. The Math.max() will correctly choose to start a new sequence! Kadane’s “Reset to 0” rule is just a highly optimized, readable manifestation of this exact Math.max logic.

Interview Questions

Q: What if the interviewer explicitly asks you to return the exact start and end indices of the winning subarray, not just the sum?
A: You can easily modify Kadane to track this! You create variables bestStart, bestEnd, and tempStart.
Whenever you reset the backpack to 0, you update tempStart = i + 1.
Whenever you beat the global maxScore, you instantly copy bestStart = tempStart and bestEnd = i.
At the end of the loop, [bestStart, bestEnd] perfectly bounds the winning subarray!

Q: A developer uses the sliding window technique (a left and right pointer) to solve this. Is that correct?
A: No, this is a famous trap. The Sliding Window technique requires a distinct “Invalidation Condition” to know exactly when to shrink the left pointer (e.g., “Shrink if the sum exceeds 10”). Because this array contains both positive and negative numbers, the sum wildly fluctuates up and down. A negative number doesn’t “invalidate” the window (because a massive +100 could be sitting right behind it!). Sliding Window fails completely. Kadane’s Algorithm is mandatory.