Maximum Subarray

Given an array of integers, find the contiguous subarray with the largest sum. Brute-force over all subarrays is O(n^2).

Why this is worth learning

The useful state is the best nonempty subarray ending exactly here, not the best subarray anywhere. A negative preceding sum can only hurt a segment that includes the current value.

Before coding: one-minute experiment

For [-5,-2,-8], what is the answer and why is initializing the answer to zero incorrect?

Function signature

func MaxSubArray(nums []int) int

Inputs / outputs

• nums: non-empty array of integers.
• Return: maximum subarray sum.

Example

nums = [-2,1,-3,4,-1,2,1,-5,4]
Best subarray: [4,-1,2,1] -> 6
Output: 6

Constraints

• 1 <= len(nums) <= 100_000
• Values are Go int; the mathematical maximum subarray sum is guaranteed to fit int on the target.
• The input is read-only. Negative sums of discarded subarrays need not fit int.

Core idea (near-solution)

Kadane's algorithm: track the best subarray ending at each position.

Invariant: cur is the best sum of a subarray that must end at i.

Algorithm (step-by-step)

1. Initialize cur = best = nums[0].
2. For each i from 1..:
   • If cur < 0, reset cur = nums[i] before doing any addition.
   • Otherwise extend: cur += nums[i].
   • best = max(best, cur).
3. Return best.

Correctness sketch

Every nonempty subarray ending at index i is either the singleton nums[i] or an extension of a subarray ending at i-1. Among extensions, the previous maximum ending sum gives the largest total because the same nums[i] is added to every candidate. Thus E(i)=max(nums[i],E(i-1)+nums[i]). A separate best value takes the maximum of E over all processed endpoints, covering every possible nonempty subarray. Initializing both states from nums[0], rather than zero, preserves the required nonempty choice when all values are negative.

Implement the mathematical maximum by branching before addition. If cur < 0, extending is always worse than taking the new value alone, so that losing sum need not be evaluated. Otherwise cur + nums[i] cannot underflow, and it cannot exceed the representable global maximum promised by the input contract. This preserves the recurrence without requiring every discarded subarray sum to fit.

Trace (hand walkthrough)

Example input:
nums = [-2,1,-3,4,-1,2,1,-5,4]
Best subarray: [4,-1,2,1] -> 6
Output: 6

Walk:
- cur=-2 best=-2
- val=1 -> cur=1 best=1; val=-3 -> cur=-2
- val=4 -> cur=4 best=4; val=-1 -> cur=3
- val=2 -> cur=5; val=1 -> cur=6 best=6

Pitfalls to avoid

• Initializing cur to 0 (fails for all-negative arrays).
• Confusing subarray (contiguous) with subsequence.
• Eagerly computing max(x, cur+x) in fixed-width arithmetic. On a 64-bit target, [-9223372036854775808,-1] has answer -1, but the discarded addition wraps to 9223372036854775807.

Debugging lens

Test all-negative inputs, one value, zeros, and a reset after the smallest representable integer. The recurrence is about subarrays, not arbitrary subsequences. Reset before computing a losing negative extension.

Complexity

• Time: O(n).
• Extra space: O(1).

Implementation notes (Go)

• Use int and branch before adding. The maximum answer must fit the target int; the function does not report overflow for inputs outside that guarantee.

Reconstruction checkpoint

For [-5,-2,-8], what is the answer and why is initializing the answer to zero incorrect?

Return to 1D DP (Including Kadane) · Module quiz