53. Maximum Subarray (Medium)

Problem

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

Example

• nums = [-2,1,-3,4,-1,2,1,-5,4] → 6 (subarray [4,-1,2,1])
• nums = [1] → 1
• nums = [5,4,-1,7,8] → 23

LeetCode 53 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, every subarray

Python

def max_subarray(nums):
    best = nums[0]                      # L1: O(1)
    for i in range(len(nums)):          # L2: outer loop, n iterations
        total = 0
        for j in range(i, len(nums)):   # L3: inner loop, n-i iterations
            total += nums[j]            # L4: O(1)
            best = max(best, total)     # L5: O(1)
    return best

TypeScript

function maxSubarray(nums: number[]): number {
    let best = nums[0];                                    // L1: O(1)
    for (let i = 0; i < nums.length; i++) {               // L2: outer loop, n iterations
        let total = 0;
        for (let j = i; j < nums.length; j++) {           // L3: inner loop, n-i iterations
            total += nums[j];                              // L4: O(1)
            best = Math.max(best, total);                  // L5: O(1)
        }
    }
    return best;
}

Go

func maxSubArray(nums []int) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    best := nums[0]                      // L1: O(1)
    for i := 0; i < len(nums); i++ {    // L2: outer loop, n iterations
        total := 0
        for j := i; j < len(nums); j++ { // L3: inner loop, n-i iterations
            total += nums[j]             // L4: O(1)
            best = max(best, total)      // L5: O(1)
        }
    }
    return best
}

Swift

final class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var best = nums[0]
        for start in nums.indices {
            var sum = 0
            for end in start..<nums.count { sum += nums[end]; best = max(best, sum) }
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (outer loop)	$O(1)$	n	$O(n)$
L3, L4, L5 (inner loop)	$O(1)$	n(n+1)/2 total	$O(n²)$ ← dominates

Every (i, j) subarray pair is visited exactly once; there are n(n+1)/2 such pairs.

Complexity

• Time: $O(n²)$, driven by L3/L4/L5 (the nested loop over all start/end pairs).
• Space: $O(1)$.

Approach 2: Divide and conquer

Split in half; combine: max is entirely left, entirely right, or spans the midpoint (compute best suffix of left + best prefix of right).

Python

def max_subarray(nums):
    def helper(lo, hi):                             # L1: called O(n) times total
        if lo == hi:
            return nums[lo]                         # L2: O(1) base case
        mid = (lo + hi) // 2                        # L3: O(1)
        left_max = helper(lo, mid)                  # L4: recurse left half
        right_max = helper(mid + 1, hi)             # L5: recurse right half

        left_suffix = right_prefix = float('-inf')
        total = 0
        for i in range(mid, lo - 1, -1):            # L6: scan left half O(n/2)
            total += nums[i]
            left_suffix = max(left_suffix, total)
        total = 0
        for i in range(mid + 1, hi + 1):            # L7: scan right half O(n/2)
            total += nums[i]
            right_prefix = max(right_prefix, total)

        return max(left_max, right_max, left_suffix + right_prefix)
    return helper(0, len(nums) - 1)

TypeScript

function maxSubarray(nums: number[]): number {
    function helper(lo: number, hi: number): number {   // L1: called O(n) times total
        if (lo === hi) return nums[lo];                 // L2: O(1) base case
        const mid = (lo + hi) >> 1;                    // L3: O(1)
        const leftMax = helper(lo, mid);               // L4: recurse left half
        const rightMax = helper(mid + 1, hi);          // L5: recurse right half

        let leftSuffix = -Infinity;
        let total = 0;
        for (let i = mid; i >= lo; i--) {              // L6: scan left half O(n/2)
            total += nums[i];
            if (total > leftSuffix) leftSuffix = total;
        }
        let rightPrefix = -Infinity;
        total = 0;
        for (let i = mid + 1; i <= hi; i++) {          // L7: scan right half O(n/2)
            total += nums[i];
            if (total > rightPrefix) rightPrefix = total;
        }
        return Math.max(leftMax, rightMax, leftSuffix + rightPrefix);
    }
    return helper(0, nums.length - 1);
}

Go

func maxSubArray(nums []int) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    var helper func(lo, hi int) int
    helper = func(lo, hi int) int {                     // L1: called O(n) times total
        if lo == hi { return nums[lo] }                 // L2: O(1) base case
        mid := (lo + hi) / 2                            // L3: O(1)
        leftMax := helper(lo, mid)                      // L4: recurse left half
        rightMax := helper(mid+1, hi)                   // L5: recurse right half
        leftSuffix := -1 << 62
        total := 0
        for i := mid; i >= lo; i-- {                    // L6: scan left half O(n/2)
            total += nums[i]
            leftSuffix = max(leftSuffix, total)
        }
        rightPrefix := -1 << 62
        total = 0
        for i := mid + 1; i <= hi; i++ {                // L7: scan right half O(n/2)
            total += nums[i]
            rightPrefix = max(rightPrefix, total)
        }
        return max(max(leftMax, rightMax), leftSuffix+rightPrefix)
    }
    return helper(0, len(nums)-1)
}

Swift

final class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        func solve(_ low: Int, _ high: Int) -> Int {
            if low == high { return nums[low] }
            let mid = (low + high) / 2
            var leftSum = Int.min, sum = 0
            for index in stride(from: mid, through: low, by: -1) { sum += nums[index]; leftSum = max(leftSum, sum) }
            var rightSum = Int.min
            sum = 0
            for index in (mid + 1)...high { sum += nums[index]; rightSum = max(rightSum, sum) }
            return max(solve(low, mid), solve(mid + 1, high), leftSum + rightSum)
        }
        return solve(0, nums.count - 1)
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L4, L5 (recursion)	T(n/2) each	log n levels	drives recurrence
L6, L7 (cross-sum scan)	$O(n)$	at each level	$O(n log n)$ ← dominates

The recurrence is T(n) = 2T(n/2) + $O(n)$, which solves to $O(n log n)$ by the Master Theorem (case 2).

Complexity

• Time: $O(n log n)$, driven by L6/L7 (the cross-midpoint scan repeated at each recursion level).
• Space: $O(log n)$ recursion stack depth.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Kadane’s algorithm (optimal greedy)

Keep a running sum. If it goes negative, reset to 0, no point carrying negative baggage forward.

Python

def max_subarray(nums):
    best = cur = nums[0]        # L1: O(1)
    for x in nums[1:]:          # L2: single pass, n-1 iterations
        cur = max(x, cur + x)   # L3: greedy choice: extend or restart
        best = max(best, cur)   # L4: track global best
    return best

TypeScript

function maxSubarray(nums: number[]): number {
    let best = nums[0];                                    // L1: O(1)
    let cur = nums[0];
    for (let i = 1; i < nums.length; i++) {               // L2: single pass, n-1 iterations
        const x = nums[i];
        cur = Math.max(x, cur + x);                        // L3: greedy choice: extend or restart
        best = Math.max(best, cur);                        // L4: track global best
    }
    return best;
}

Go

func maxSubArray(nums []int) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    best := nums[0]                       // L1: O(1)
    cur := nums[0]
    for _, x := range nums[1:] {          // L2: single pass, n-1 iterations
        cur = max(x, cur+x)               // L3: greedy choice: extend or restart
        best = max(best, cur)             // L4: track global best
    }
    return best
}

Swift

final class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var current = nums[0], best = nums[0]
        for value in nums.dropFirst() { current = max(value, current + value); best = max(best, current) }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2, L3, L4 (loop)	$O(1)$	n-1	$O(n)$ ← dominates

A single pass; each element is touched exactly once.

Complexity

• Time: $O(n)$, driven by L2/L3/L4 (the single linear scan).
• Space: $O(1)$.

Why greedy works

At each position, the best subarray ending here is either “extend the previous best” or “start fresh from here.” That’s it, a greedy choice (restart vs. extend) at every index suffices, because a negative running total can only hurt future extensions.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Every subarray	$O(n²)$	$O(1)$
Divide and conquer	$O(n log n)$	$O(log n)$
Kadane’s algorithm	$O(n)$	$O(1)$

Kadane’s is the canonical answer. Same template: Maximum Product Subarray (152) needs a twist (track max AND min); Best Time to Buy/Sell Stock (121) is Kadane on price differences.

Test cases

Go

func maxSubArray(nums []int) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    best := nums[0]
    cur := nums[0]
    for _, x := range nums[1:] {
        cur = max(x, cur+x)
        best = max(best, cur)
    }
    return best
}

Python

# Quick smoke tests, paste into a REPL or save as test_053.py and run.
# Uses the canonical implementation (Approach 3: Kadane's algorithm).

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

def _run_tests():
    assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
    assert max_subarray([1]) == 1
    assert max_subarray([5, 4, -1, 7, 8]) == 23
    assert max_subarray([-1]) == -1                # all negative, single element
    assert max_subarray([-2, -3, -1, -5]) == -1    # all negative, pick least bad
    assert max_subarray([1, 2, 3, 4, 5]) == 15     # all positive, whole array
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function maxSubarray(nums: number[]): number {
    let best = nums[0];
    let cur = nums[0];
    for (let i = 1; i < nums.length; i++) {
        const x = nums[i];
        cur = Math.max(x, cur + x);
        best = Math.max(best, cur);
    }
    return best;
}

console.assert(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) === 6);
console.assert(maxSubarray([1]) === 1);
console.assert(maxSubarray([5, 4, -1, 7, 8]) === 23);
console.assert(maxSubarray([-1]) === -1);          // all negative, single element
console.assert(maxSubarray([-2, -3, -1, -5]) === -1);  // all negative, pick least bad
console.assert(maxSubarray([1, 2, 3, 4, 5]) === 15);   // all positive, whole array
console.log("all tests pass");

Related data structures

• Arrays, input; running sum

Related concepts

• Greedy Algorithms, the local choice pattern protected by an invariant about the best reachable future.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.