Maximum Subarray

Problem

Given an integer array nums, find the contiguous subarray (containing at least one element) with the largest sum, and return that sum. The subarray must be a single unbroken run of elements.

Examples

• nums = [-2,1,-3,4,-1,2,1,-5,4] → 6 — the subarray [4,-1,2,1] sums to 6, the best possible.
• nums = [1] → 1 — the only subarray.
• nums = [-3,-1,-2] → -1 — all negative, so the best is the single largest element -1 (a subarray must be non-empty).

Constraints

• 1 <= len(nums) <= 10^5
• -10^4 <= nums[i] <= 10^4

O(n) is expected. The all-negative case is the classic edge case: you must return the least-bad single element, not 0.

Think about it first

TL;DR

Kadane’s algorithm: keep the best subarray sum ending at each position, restarting whenever the running sum turns negative — O(n) time, O(1) space.

Approach 1 — Brute force: every subarray

Try all O(n^2) start/end pairs, summing each with a running inner total.

from typing import List

def maxSubArray(nums: List[int]) -> int:
    n = len(nums)
    best = nums[0]
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            best = max(best, total)
    return best

Complexity: O(n^2) time, O(1) space. At n = 10^5 that is 10^10 additions — too slow.

Approach 2 — Kadane’s algorithm (DP, then greedy)

The DP view: let dp[i] = the largest sum of a subarray ending exactly at index i. Either you extend the best subarray ending at i-1, or you start anew at i:

dp[i] = max(nums[i], dp[i-1] + nums[i]), and the answer is max(dp).

The greedy-choice property (why the local restart is globally optimal): the recurrence reduces to a local decision — keep the previous run only if it helps. If dp[i-1] < 0, then dp[i-1] + nums[i] < nums[i], so drop the prefix and restart at nums[i]; if dp[i-1] >= 0, extend. A negative running prefix can only lower the sum of any subarray that reaches past it, so discarding it is never worse. Because each position’s optimal “ending here” value depends only on the previous one, we collapse the DP array to a single rolling variable cur, giving O(1) space.

from typing import List

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

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

Result 6, the subarray [4,-1,2,1]. At x=4 the negative cur=-2 is discarded, which is the greedy restart.

Complexity: O(n) time, O(1) space.

Approach 3 — Divide and conquer

The maximum subarray either lies entirely in the left half, entirely in the right half, or crosses the midpoint. Recurse on both halves and separately compute the best crossing sum (best suffix of the left plus best prefix of the right), then take the max of the three.

from typing import List

def maxSubArray(nums: List[int]) -> int:
    def best(lo: int, hi: int) -> int:
        if lo == hi:
            return nums[lo]
        mid = (lo + hi) // 2
        left = best(lo, mid)
        right = best(mid + 1, hi)
        # best suffix ending at mid
        s = 0
        left_cross = nums[mid]
        for i in range(mid, lo - 1, -1):
            s += nums[i]
            left_cross = max(left_cross, s)
        # best prefix starting at mid+1
        s = 0
        right_cross = nums[mid + 1]
        for i in range(mid + 1, hi + 1):
            s += nums[i]
            right_cross = max(right_cross, s)
        return max(left, right, left_cross + right_cross)

    return best(0, len(nums) - 1)

Complexity: O(n log n) time, O(log n) recursion space. Slower than Kadane but a classic interview follow-up and the basis for a segment-tree version supporting updates.

Common pitfalls

• Initializing best = 0. On an all-negative array that wrongly returns 0; a non-empty subarray must be chosen, so seed best and cur from nums[0].
• Writing cur = cur + x without the max(x, ...) — you fail to restart and drag negative prefixes forward.
• In divide-and-conquer, forgetting that the crossing sum must include the midpoint elements on both sides (it cannot be empty on either half).

Pattern takeaway

For “best contiguous run” problems, carry one rolling value — the best answer ending at the current element — and drop it whenever it turns counterproductive (here, when it goes negative). The same reset-when-the-prefix-hurts idea applies to max-product, longest-positive-run, and many streaming problems.