Maximum Subarray — Kadane's Algorithm and the DP Behind It

Problem Statement#

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Constraints:

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

Example 1:

Input:  nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The subarray [4, -1, 2, 1] has the largest sum 6.

Example 2:

Input:  nums = [1]
Output: 1
Explanation: Only one element.

Example 3:

Input:  nums = [5, 4, -1, 7, 8]
Output: 23
Explanation: The entire array is the subarray with maximum sum.

Why This Problem Matters#

Maximum Subarray (LeetCode 53) is arguably the most important contiguous-subarray problem in all of dynamic programming. The underlying insight — "at each position, extend or restart" — is the seed of Kadane's Algorithm, a technique that surfaces in finance (maximum profit windows), signal processing (maximum energy segments), and competitive programming alike.

Amazon, Google, and Microsoft list it as a core interview problem. It appears in the Blind 75 problem set and every major DP curriculum for good reason: it is a clean O(n) DP that the vast majority of programmers initially solve with brute force O(n^2) or O(n^3), making it an excellent filter for algorithmic thinking.

Beyond the base problem, the "extend or restart" pattern generalizes to Maximum Product Subarray (LC 152), Maximum Sum Circular Subarray (LC 918), and any problem asking for the optimal contiguous segment in a sequence.

The Core Insight#

Define dp[i] as the maximum sum of a subarray that ends at index i. Then:

dp[i] = max(nums[i], dp[i-1] + nums[i])

Read it as: "the best subarray ending at index i is either just nums[i] alone (start fresh), or nums[i] appended to the best subarray ending at i-1 (extend)."

If dp[i-1] is negative, extending is harmful — you are better off starting a new subarray at i. If dp[i-1] is non-negative, extending is always at least as good.

The answer is max(dp[0], dp[1], ..., dp[n-1]) — the best ending position might be anywhere in the array.

Optimal substructure: dp[i] depends only on dp[i-1] and the current element.

Overlapping subproblems: a naive O(n^2) approach recomputes many subarray sums redundantly.

Building the DP Solution#

Step 1 — Brute Force (O(n^2))#

# Python — brute force, O(n^2) — illustrative only
def maxSubArray(nums):
    n = len(nums)
    best = float('-inf')
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j]
            best = max(best, current_sum)
    return best

// JavaScript — brute force, O(n^2)
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];
            best = Math.max(best, currentSum);
        }
    }
    return best;
}

Step 2 — Top-Down Memoization (O(n) time, O(n) space)#

# Python — top-down memoization on dp[i] = max subarray sum ending at i
from functools import lru_cache
 
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        n = len(nums)
 
        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i == 0:
                return nums[0]
            return max(nums[i], dp(i - 1) + nums[i])
 
        return max(dp(i) for i in range(n))

// JavaScript — top-down memoization
var maxSubArray = function(nums) {
    const n = nums.length;
    const memo = new Map();
 
    function dp(i) {
        if (i === 0) return nums[0];
        if (memo.has(i)) return memo.get(i);
        const result = Math.max(nums[i], dp(i - 1) + nums[i]);
        memo.set(i, result);
        return result;
    }
 
    let best = -Infinity;
    for (let i = 0; i < n; i++) best = Math.max(best, dp(i));
    return best;
};

Step 3 — Bottom-Up Tabulation (O(n) time, O(n) space)#

# Python — bottom-up tabulation
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
        return max(dp)

// JavaScript — bottom-up tabulation
var maxSubArray = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(0);
    dp[0] = nums[0];
    for (let i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
    }
    return Math.max(...dp);
};

Optimized Solution#

Since dp[i] depends only on dp[i-1], compress to a single running variable — this is the classic Kadane's Algorithm:

# Python — Kadane's Algorithm, O(n) time, O(1) space
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        current_sum = best = nums[0]
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            best = max(best, current_sum)
        return best

// JavaScript — Kadane's Algorithm, O(n) time, O(1) space
var maxSubArray = function(nums) {
    let currentSum = nums[0], best = nums[0];
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        best = Math.max(best, currentSum);
    }
    return best;
};

Visual Dry Run#

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

Answer: 6. The subarray [4, -1, 2, 1] (indices 3 through 6) achieves this sum.

Notice that at index 1, the algorithm restarts from 1 rather than extending the -2 subarray. At index 3, it restarts again from 4, abandoning the -2 running sum.

Complexity Analysis#

Common Mistakes#

1. Initializing current_sum = 0 instead of nums[0]. If all elements are negative, the answer is the least negative element. Starting from 0 would incorrectly return 0, claiming an empty subarray which the problem disallows.

2. Initializing best = 0 instead of nums[0]. Same issue — a problem with all-negative inputs returns 0 incorrectly.

3. Taking max(0, current_sum + nums[i]) instead of max(nums[i], current_sum + nums[i]). The max(0, ...) formulation works when empty subarrays are allowed (sum 0) but is wrong here.

4. Not updating best at every step. The maximum subarray does not have to end at the last element. Update best = max(best, current_sum) on every iteration.

5. Confusing this with the maximum subarray product. Maximum Subarray (LC 53) uses sum — and negative plus positive reduces the sum. Maximum Product Subarray (LC 152) uses multiplication — and negative times negative becomes positive, requiring tracking both min and max.

6. Returning the wrong value when n = 1. For a single element, current_sum = best = nums[0] and the loop does not execute. The answer is nums[0] — correctly returned without additional guards.

Interview Tips#

Name Kadane's Algorithm explicitly. Interviewers appreciate knowing you recognize the classic algorithm. Say: "This is Kadane's Algorithm — at each position I decide whether to extend the current subarray or start fresh."

Explain the DP framing first. Describe the DP state: "I define dp[i] as the maximum subarray sum ending at index i. The recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i])." Then derive the space optimization naturally.

Handle all-negative inputs explicitly. Tell your interviewer: "I initialize current_sum and best to nums[0], not 0, to correctly handle inputs where all elements are negative."

Mention the divide-and-conquer variant. Kadane's is O(n), but there exists a divide-and-conquer O(n log n) approach for interviews asking for an alternative. It splits the array, finds the max subarray crossing the midpoint, and recurses on both halves.

Connect to follow-ups. "The same 'extend or restart' insight drives Maximum Product Subarray (LC 152) and Maximum Sum Circular Subarray (LC 918), which wraps the array."

Follow-up Questions#

Q: What if the subarray must have length at least k? Use a sliding window combined with prefix sums. The Kadane's approach does not directly apply with a minimum length constraint.

Q: What if you want to return the actual subarray, not just the sum? Track start, end, and temp_start indices. When you reset current_sum = nums[i], update temp_start = i. When current_sum > best, update start = temp_start and end = i.

Q: What about Maximum Sum Circular Subarray (LC 918)? The answer is either the max subarray in a linear sense (Kadane's), or the total sum minus the minimum subarray (the "wrap-around" case). Take the max of both.

Q: Can you solve it in O(n log n) using divide and conquer? Yes — divide at midpoint, find max crossing subarray in O(n), recurse on both halves. Useful as an alternative approach to discuss in interviews.

Q: What if there are constraints on which indices you can include? Sliding window or segment tree approaches may apply, depending on the constraint type.

Key Takeaways#

• Define dp[i] as the maximum subarray sum ending at index i. The recurrence dp[i] = max(nums[i], dp[i-1] + nums[i]) says: start fresh at i, or extend the previous best subarray.
• If dp[i-1] is negative, extending it is always worse — restart from nums[i].
• Track a global best = max(dp[0], ..., dp[n-1]) across all positions, since the optimal subarray can end anywhere.
• Always initialize current_sum and best to nums[0], not 0 — the problem requires a non-empty subarray.
• Kadane's Algorithm is O(n) time, O(1) space — the gold standard for this family of problems.
• The "extend or restart" pattern generalizes to Maximum Product Subarray (track min and max), Maximum Sum Circular Subarray (subtract minimum), and any contiguous-segment optimization problem.