Problem statement

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

Example 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] sums to 6.

Example 2

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

Constraints

• 1 <= nums.length <= 30
• -100 <= nums[i] <= 100

Hints for Maximum Subarray

1. Hint 1

   Kadane: best subarray ending here = max(x, previous best ending + x).

2. Hint 2

   Track the global maximum as you sweep.

How to solve Maximum Subarray

Kadane's algorithm. Sweep the array asking one question at each position: is it better to extend the best subarray ending at the previous index, or to start fresh here? The answer is local — extend only if the running sum is still helping — and the global best is the largest of those per-position bests.

Approach

1. Seed both the running sum and the best answer with the first element.
2. For each later element, set cur = max(element, cur + element).
3. Update best = max(best, cur).
4. Return best after the sweep.

Why it works

cur is exactly the largest sum of a subarray ending at the current index. Such a subarray either is the single element or extends the best one ending at the previous index — nothing else is possible, since it must be contiguous. Taking the maximum of these values over all endpoints therefore covers every subarray exactly once, which is why one pass suffices. Restarting when the running sum turns negative is the same statement: a negative prefix can only hurt whatever follows.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Seed with nums[0], not 0. An all-negative array must return its largest (least negative) element, and a zero seed wrongly returns 0.
• The subarray must be non-empty, which is what makes the seeding matter.
• Update best on every step, not only when restarting.
• cur = max(element, cur + element) — comparing against the element itself is what performs the restart.

Reference solution

Python

from typing import List

def maxSubArray(nums: List[int]) -> int:
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

Java

public static int maxSubArray(int[] nums) {
    int cur = nums[0], best = nums[0];
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);
        if (cur > best) best = cur;
    }
    return best;
}

C++

int maxSubArray(vector<int>& nums) {
    int cur = nums[0], best = nums[0];
    for (int i = 1; i < (int) nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);
        if (cur > best) best = cur;
    }
    return best;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium