LeetCode 53 · Medium · Greedy

Maximum Subarray

Given an integer array nums, find the contiguous, non-empty run of elements with the largest total and return that total.

O(n)time
O(1)space
Kadanedrop a negative prefix

comma-separated integers · 1–12 values · each −99 to 99

curSum after each index

public int maxSubArray(int[] nums) { int maxSub = nums[0]; int curSum = 0; for (int n : nums) { if (curSum < 0) { // a negative prefix only hurts curSum = 0; } curSum += n; maxSub = Math.max(maxSub, curSum); } return maxSub;}
i
—
n
—
curSum
0
maxSub
—
window
—

Why it works

  1. Brute force sums every subarray: fix a start, extend the end, track the best. O(n²) with a running sum, O(n³) without.
  2. A negative prefix never helps. If the run ending just before n sums below zero, any subarray that keeps it is beaten by the same subarray without it. So reset curSum to 0 and start fresh at n.
  3. Invariant: after each index, curSum is the best sum of a subarray that ends exactly there. The answer ends somewhere, so the max over all indices is the answer. One pass, two numbers: O(n) time, O(1) space.
  4. Pitfall: start maxSub at nums[0], not 0. With all negatives, [-3,-1,-2], the answer is -1: the subarray must be non-empty.
  5. Related: this is DP with the table squeezed to one cell: bestEnd[i] = Math.max(nums[i], bestEnd[i-1] + nums[i]). The same reset idea drives Gas Station (134), and the product version, 152, also tracks a running minimum.