Maximum Subarray — Kadane's Algorithm Explained (The Right Way) [Google, Amazon, Meta]

Problem Statement

Given an integer array nums, find the subarray with the largest sum and return its sum. A subarray is a contiguous non-empty sequence of elements.

Examples:

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Reason: Subarray [4, -1, 2, 1] has sum 4 + (-1) + 2 + 1 = 6

Input:  [1]
Output: 1
Reason: Single-element array — only choice is the element itself

Input:  [-3, -1, -2]
Output: -1
Reason: All elements are negative — must pick the least-negative one
        (many buggy solutions return 0 here — see "The Critical Mistake" below)

Constraints: 1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4

• Why This Problem Matters
• The "Aha" Moment — Building the Insight Without Code
• The Critical Mistake Everyone Makes
• Visual Dry Run — Full Trace
• Pattern Recognition — Local vs. Global Optimum
• Solutions
• Brute Force — O(n²) time, O(1) space
• Kadane's Algorithm — O(n) time, O(1) space
• Bonus: Divide and Conquer — O(n log n) time, O(log n) space
• Returning the Actual Subarray — The Most Common Follow-up
• Complexity Analysis
• Follow-up Questions — What FAANG Actually Asks
• 1. Maximum Sum Circular Subarray (LeetCode 918) — Medium
• 2. Maximum Product Subarray (LeetCode 152) — Medium
• 3. Return the Actual Subarray
• 4. Maximum Subarray of Size at Least K
• 5. K-Concatenation Maximum Sum (LeetCode 1191) — Medium
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 53 appears on Blind 75, NeetCode 150, and virtually every "must-solve" FAANG prep list — and for good reason. It is not actually testing whether you can code a loop. It is testing a fundamental thinking pattern:

Can you recognize when a locally suboptimal state (negative running sum) should be abandoned instead of carried forward?

This "extend or restart" decision recurs across dozens of harder problems: maximum product subarray, largest rectangle, buy/sell with cooldown, and more. Master the mental model here, and you get all of them for free.

Interview frequency: This problem or a direct variant (circular subarray, product version, returning the actual subarray) shows up in roughly 1 in 5 array-heavy FAANG interviews according to community reports on Blind and LeetCode Discuss. Google and Amazon are the most frequent askers; Meta often asks it as a warm-up before a harder DP problem.

The "Aha" Moment — Building the Insight Without Code

Before touching any syntax, let us think like an interviewer who invented this problem.

Imagine you are walking along the array left-to-right, holding a running tab of your current subarray's sum. At each new number, you face exactly one binary decision:

"Should I attach this number to my current subarray, or tear it up and start fresh here?"

When does starting fresh win? Precisely when your running tab is negative. Why? Because a negative running sum is a liability — it only drags down whatever you attach it to. If your current tab is -5 and the next number is 3, your best subarray ending at this position is just [3] (sum = 3), not the extended subarray (sum = -5 + 3 = -2).

If your current tab is +2 and the next number is -1, extending is fine — you end up at +1, which is better than restarting at just -1.

Think of it like a business running total. You are measuring cumulative profit/loss over a stretch of trading days. The moment your cumulative loss from the current stretch exceeds any future gain, you cut your losses and open a new position. You never let a negative historical drag reduce your future earnings.

This decision — made independently at every position — is simultaneously a greedy choice (locally optimal) and a DP choice (built on the optimal solution to the previous subproblem). That dual nature is why interviewers argue about whether Kadane's is greedy or DP. The correct answer: it is both.

The two variables you need:

• cur — the maximum sum of any subarray ending exactly at the current index
• best — the maximum sum seen across all positions so far

At each position x:

• cur = max(x, cur + x) — either start fresh at x, or extend the previous best
• best = max(best, cur) — keep the global champion

The Critical Mistake Everyone Makes

Here is the bug that appears in roughly half of all first-attempt solutions:

# WRONG — fails on all-negative arrays
cur  = 0
best = 0

for x in nums:
    cur  = max(0, cur + x)   # <-- BUG: resets to 0, not to x
    best = max(best, cur)

Test it against [-3, -1, -2]:

The code returns 0 — but the correct answer is -1.

Why does this happen? Resetting to 0 implicitly assumes an empty subarray is allowed (sum = 0). But the problem requires at least one element. On an all-negative array, every element is negative, so the "reset to 0" path is always taken, and the algorithm never picks any element.

The fix is conceptually simple: when you start fresh, you start at the current element, not at zero.

# CORRECT
cur  = nums[0]
best = nums[0]

for x in nums[1:]:
    cur  = max(x, cur + x)   # start fresh at x, or extend
    best = max(best, cur)

Now for [-3, -1, -2]:

Returns -1. Correct.

The one-line rule: Initialize cur and best to nums[0], start your loop at index 1, and use max(x, cur + x) — never max(0, cur + x).

Visual Dry Run — Full Trace

Let us trace the classic example [-2, 1, -3, 4, -1, 2, 1, -5, 4] step by step.

Answer: 6 — corresponding to subarray [4, -1, 2, 1] (indices 3–6).

Key observations from the trace:

• At index 1, the running sum went negative (-2), so we ditched it and restarted at 1.
• At index 3, again the running sum (-2) was worse than just taking 4 alone — fresh start.
• From index 3 onward, extending kept winning until best hit 6 at index 6.
• The trailing -5, 4 pulled cur down but never beat the stored best.

Pattern Recognition — Local vs. Global Optimum

This problem is the textbook example of a "local vs. global optimum" DP pattern:

dp[i] = max sum of any subarray ending at index i
      = max(nums[i], dp[i-1] + nums[i])

We do not need to store the full dp array because dp[i] only depends on dp[i-1]. So we compress it to a single variable cur. The global answer is max(dp[0], dp[1], ..., dp[n-1]) — tracked continuously in best.

This exact structure appears in:

• Maximum Product Subarray (track cur_min and cur_max instead)
• Longest Increasing Subsequence (with a different transition function)
• Buy/sell stock problems (reformulate as max subarray of daily changes)
• Best time series segmentation problems

Whenever you see "find the best contiguous something," think: "what is the best ending exactly here, and how does it relate to what came before?"

Solutions

Brute Force — O(n²) time, O(1) space

Check every possible subarray. Useful to state upfront in interviews to show you understand the naive approach before optimizing.

Python:

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        best = float('-inf')
        
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]          # extend subarray [i..j]
                best = max(best, current_sum)    # track global max
        
        return best

JavaScript:

function maxSubArray(nums) {
    let best = -Infinity;
    
    for (let i = 0; i < nums.length; i++) {
        let currentSum = 0;
        for (let j = i; j < nums.length; j++) {
            currentSum += nums[j];              // extend subarray [i..j]
            best = Math.max(best, currentSum);  // track global max
        }
    }
    
    return best;
}

Kadane's Algorithm — O(n) time, O(1) space

The optimal solution. This is what every FAANG interviewer expects.

Python:

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # Initialize to first element — handles all-negative arrays correctly
        cur = best = nums[0]
        
        for x in nums[1:]:
            # Key decision: start fresh at x, or extend previous subarray?
            # Starting fresh wins when cur is negative (cur + x < x)
            cur  = max(x, cur + x)
            best = max(best, cur)
        
        return best

JavaScript:

function maxSubArray(nums) {
    // Initialize to first element — handles all-negative arrays correctly
    let cur = nums[0];
    let best = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // Start fresh at nums[i], or extend the previous running subarray?
        cur  = Math.max(nums[i], cur + nums[i]);
        best = Math.max(best, cur);
    }
    
    return best;
}

Bonus: Divide and Conquer — O(n log n) time, O(log n) space

Interviewers occasionally ask: "Can you solve this without Kadane's? Think divide and conquer." This is the approach from Introduction to Algorithms (CLRS). It is slower, but demonstrates breadth.

Core idea: Split the array at the midpoint. The maximum subarray either:

1. Lives entirely in the left half
2. Lives entirely in the right half
3. Crosses the midpoint (includes elements from both sides)

Cases 1 and 2 are solved recursively. Case 3 is solved by finding the best suffix ending at mid and the best prefix starting at mid+1, then summing them.

Python:

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def helper(left: int, right: int) -> int:
            # Base case: single element
            if left == right:
                return nums[left]
            
            mid = (left + right) // 2
            
            # Recurse on left and right halves
            left_max  = helper(left, mid)
            right_max = helper(mid + 1, right)
            
            # Find max subarray crossing the midpoint
            # Best suffix of left half (extending left from mid)
            left_sum = cur = 0
            for i in range(mid, left - 1, -1):
                cur += nums[i]
                left_sum = max(left_sum, cur)
            
            # Best prefix of right half (extending right from mid+1)
            right_sum = cur = 0
            for i in range(mid + 1, right + 1):
                cur += nums[i]
                right_sum = max(right_sum, cur)
            
            cross_max = left_sum + right_sum
            
            return max(left_max, right_max, cross_max)
        
        return helper(0, len(nums) - 1)

JavaScript:

function maxSubArray(nums) {
    function helper(left, right) {
        // Base case: single element
        if (left === right) return nums[left];
        
        const mid = Math.floor((left + right) / 2);
        
        // Recurse on left and right halves
        const leftMax  = helper(left, mid);
        const rightMax = helper(mid + 1, right);
        
        // Find max subarray crossing the midpoint
        // Best suffix of left half
        let leftSum = 0, cur = 0;
        for (let i = mid; i >= left; i--) {
            cur += nums[i];
            leftSum = Math.max(leftSum, cur);
        }
        
        // Best prefix of right half
        let rightSum = 0;
        cur = 0;
        for (let i = mid + 1; i <= right; i++) {
            cur += nums[i];
            rightSum = Math.max(rightSum, cur);
        }
        
        const crossMax = leftSum + rightSum;
        
        return Math.max(leftMax, rightMax, crossMax);
    }
    
    return helper(0, nums.length - 1);
}

When would you use divide and conquer over Kadane's? Almost never in practice — it is strictly worse asymptotically. But it matters in two scenarios: (a) when an interviewer explicitly asks to demonstrate D&C thinking, and (b) in parallel computing contexts where left/right subproblems can be split across processors.

Returning the Actual Subarray — The Most Common Follow-up

After you give the O(n) Kadane's solution, roughly 60% of interviewers will ask: "Good. Now, instead of returning the sum, return the actual subarray (or its start/end indices)."

The trick is tracking a temp_start that moves whenever you restart, and committing it to start only when you find a new best.

Python:

from typing import List, Tuple

def maxSubArrayWithIndices(nums: List[int]) -> Tuple[int, int, int]:
    cur = best = nums[0]
    start = end = 0
    temp_start = 0          # candidate start for the current running subarray
    
    for i in range(1, len(nums)):
        if cur + nums[i] < nums[i]:
            # Starting fresh is better — move the candidate start
            cur = nums[i]
            temp_start = i
        else:
            # Extend the current subarray
            cur += nums[i]
        
        if cur > best:
            best = cur
            start = temp_start  # commit the candidate start
            end = i
    
    return start, end, best
    # nums[start:end+1] is the actual subarray

# Example:
# nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Returns: (3, 6, 6) → nums[3:7] = [4, -1, 2, 1], sum = 6

JavaScript:

function maxSubArrayWithIndices(nums) {
    let cur = nums[0], best = nums[0];
    let start = 0, end = 0, tempStart = 0;
    
    for (let i = 1; i < nums.length; i++) {
        if (cur + nums[i] < nums[i]) {
            // Starting fresh is better
            cur = nums[i];
            tempStart = i;
        } else {
            cur += nums[i];
        }
        
        if (cur > best) {
            best = cur;
            start = tempStart;  // commit the candidate start
            end = i;
        }
    }
    
    return { start, end, sum: best, subarray: nums.slice(start, end + 1) };
}

Complexity Analysis

For the divide and conquer recurrence: T(n) = 2T(n/2) + O(n). By the Master Theorem (case 2), this resolves to O(n log n).

Follow-up Questions — What FAANG Actually Asks

1. Maximum Sum Circular Subarray (LeetCode 918) — Medium

"What if the array is circular — the end wraps around to the beginning?"

Two cases:

• Non-wrapping: plain Kadane's on the array.
• Wrapping: the selected subarray wraps, meaning the complement (the middle part left out) is a minimum subarray. Answer = total_sum - min_subarray_sum.

Final answer: max(kadane_max, total_sum - kadane_min). Edge case: if all elements are negative, total_sum - kadane_min equals 0 (empty), so return kadane_max.

2. Maximum Product Subarray (LeetCode 152) — Medium

"Same problem but multiply instead of add."

A negative times a negative becomes positive — so you cannot throw away negative running products. Track both cur_max and cur_min at every step. When you see a negative number, swap them.

3. Return the Actual Subarray

Already covered above. Track temp_start and commit to start on every new best.

4. Maximum Subarray of Size at Least K

"Find the max subarray sum with length >= k."

Precompute prefix sums. For each end index i >= k, the answer is prefix[i+1] - min(prefix[0..i-k+1]). Maintain a running minimum of prefix[j] for valid starting positions.

5. K-Concatenation Maximum Sum (LeetCode 1191) — Medium

"If you repeat the array k times, find the max subarray sum."

• If k == 1: plain Kadane's.
• If k >= 2: the answer is max(Kadane(arr * 2), Kadane(arr) + (k - 2) * max(0, total_sum)). If the total array sum is positive, extra copies contribute (k-2) * total_sum.

This Pattern Solves

Other problems that use the same "extend or restart" local-global DP structure:

Key Takeaway

Kadane's Algorithm is deceptively simple to code but surprisingly easy to get subtly wrong. The single most important thing to remember: initialize cur and best to nums[0], not to 0 — this is the only correct way to handle all-negative arrays, and it is the exact mistake that separates candidates who truly understand the algorithm from those who memorized a version that breaks on edge cases.

The deeper insight is the pattern itself: at every position, the optimal subarray ending there either extends from the past or starts fresh — and that one-liner decision, max(x, cur + x), encodes everything you need to know.

Next: Problem 5 — Move Zeroes →