Back to solutions

Maximum Subarray

EasyArrays

Find the largest sum of any contiguous subarray.

Open problem
Constraints
  • 1 <= n <= 10^5
  • -10^4 <= nums[i] <= 10^4

Kadane's algorithm

Time O(n)Space O(1)

Scan left to right keeping `cur`, the best sum of a subarray that ends at the current element. At each step you either extend the previous run (cur + x) or start fresh at x, whichever is larger. Track the best `cur` ever seen.

Key terms
subarray:
A contiguous (back-to-back) slice of the array. Unlike a subsequence it cannot skip elements.
cur (running sum ending here):
The largest sum of any subarray that finishes exactly at the current index.
Kadane's algorithm:
A classic dynamic-programming scan that solves maximum subarray in O(n) by reusing the best sum ending at the previous index.
int maxSubArray(vector<int>& nums) {
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);
        best = max(best, cur);
    }
    return best;
}
Step by step
  1. Start best and cur both equal to the first element (a subarray must be non-empty).
  2. For each following element x, decide whether to extend: cur = max(x, cur + x).
  3. If cur + x is smaller than x alone, the previous run was dragging us down, so we restart at x.
  4. Update best = max(best, cur) so the overall answer never drops.
  5. Return best after the scan. This also works when every number is negative because we seed with nums[0].