Maximum Subarray — InterviewPrepKit

Solving tips

This is Kadane's algorithm: keep a rolling cur = max(nums[i], cur + nums[i]) — restart whenever the running prefix turns negative since it can only drag future sums down.
Track best = max(best, cur) separately as you go.
Seed both best and cur from nums[0], never 0, so the all-negative case correctly returns the least-negative element.
Target O(n) time and O(1) space; the divide-and-conquer O(n log n) crossing-sum variant is a classic follow-up.

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

Hint 1

Scan left to right and keep a running sum of the "current best subarray ending here." When would extending that run to the current element be worse than starting fresh at the current element?

Hint 2

If the running sum has gone negative, any subarray that carries it forward is dragged down. Dropping that negative prefix and restarting at the current element is never worse.

Hint 3

This is Kadane's algorithm: cur = max(nums[i], cur + nums[i]), and track the best cur ever seen. Initialize both from nums[0] so the all-negative case is handled.

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

class Solution:
    def maxSubArray(self, 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 hides a purely local decision — keep the previous run only if it helps. Concretely, if dp[i-1] < 0, then dp[i-1] + nums[i] < nums[i], so you drop the whole prefix and restart at nums[i]; if dp[i-1] >= 0, you extend. A negative running prefix can only lower the sum of any subarray that reaches past it, so discarding it is never a mistake — no future element benefits from carrying a negative head. 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

class Solution:
    def maxSubArray(self, 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]:

x	`cur = max(x, cur+x)`	`best`
-2	-2 (init)	-2
1	max(1, -2+1=-1) = 1	1
-3	max(-3, 1-3=-2) = -2	1
4	max(4, -2+4=2) = 4	4
-1	max(-1, 4-1=3) = 3	4
2	max(2, 3+2=5) = 5	5
1	max(1, 5+1=6) = 6	6
-5	max(-5, 6-5=1) = 1	6
4	max(4, 1+4=5) = 5	6

Result 6, the subarray [4,-1,2,1]. ✅ Note how at x=4 the negative cur=-2 is discarded — the greedy restart.

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

Approach 3 — Divide and conquer

The insight: 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

class Solution:
    def maxSubArray(self, 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 greedily drop it whenever it turns counterproductive (here, negative). This “reset when the accumulated prefix hurts” instinct generalizes to max-product, longest-positive-run, and many streaming problems.