Maximum Subarray — Kadane Algorithm for FAANG Interviews

Problem Statement#

Given an integer array nums, find the contiguous subarray with the largest sum and return its sum. The subarray must contain at least one element.

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Input:  nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

Input:  nums = [5, 4, -1, 7, 8]
Output: 23

Why This Problem Matters#

Maximum Subarray is the dynamic programming gateway array interview question. Amazon, Google, and Meta use it to test whether candidates can identify a DP recurrence in linear form. The Kadane algorithm is the cleanest one-line DP in the FAANG canon.

The pattern transfers to Maximum Product Subarray, Maximum Circular Subarray Sum, and Best Time to Buy and Sell Stock. Knowing Kadane signals dynamic programming maturity without needing a 2D table.

The Core Insight#

For each index i, the maximum subarray ending exactly at i is either nums[i] alone or nums[i] plus the maximum subarray ending at i minus 1. This local maximum is Kadane.

We maintain two scalars: curr is the best subarray ending here, best is the best seen overall. Reset curr to nums[i] when extending hurts. The answer is best after one pass.

This is dynamic programming with O(1) memory because the recurrence only looks back one step.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def maxSubArray(self, nums):
        best = curr = nums[0]
        for n in nums[1:]:
            curr = max(n, curr + n)
            best = max(best, curr)
        return best

var maxSubArray = function(nums) {
    let best = nums[0];
    let curr = nums[0];
    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        best = Math.max(best, curr);
    }
    return best;
};

Time: O(n) — one pass. Space: O(1) — two scalar variables.

Common Mistakes#

• Initializing best to zero, which fails on all-negative arrays.
• Using max minus min as if it were stock profit; subarray sum is different.
• Resetting curr to zero instead of nums[i] when extending hurts.
• Skipping the first element when iterating over nums[1:].

Interview Tips#

• State brute force triple loop O(n^3), then the prefix-sum O(n^2), then Kadane.
• Identify the DP recurrence: curr at i is max of nums[i] alone, or curr at i minus 1 plus nums[i].
• Mention the divide-and-conquer alternative for the indices follow-up.
• Verbalize the negative-array edge case before coding.

Follow-up Questions#

• Return start and end indices? Hint: track when curr resets.
• Maximum product subarray? Hint: track min and max because of negatives.
• Circular array? Hint: max wrap equals total minus min subarray.
• Subarray of length k or more? Hint: prefix sum plus running min.
• 2D version, max submatrix sum? Hint: collapse columns then Kadane on rows.

Key Takeaways#

• LeetCode 53 Kadane gives O(n) time and O(1) space.
• The recurrence is curr equals max of nums[i] alone or curr plus nums[i].
• Initialize both best and curr to nums[0]; never to zero.
• Generalizes to product, circular, and 2D maximum subarray problems.
• Brute force is O(n^2); never present it as final.
• Tracking start and end indices requires recording resets.
• Most-asked DP gateway question at Amazon, Google, and Meta.