Maximum subarray (Kadane’s algorithm)

Medium TimeO(n) SpaceO(1)

Given nums, whose values may be negative, return the largest sum of any run of adjacent values — a subarray, not a subsequence. The run may not be empty, so when every value is negative the answer is the least negative one.

Examples

Example 1

Input
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output
6
4 + (−1) + 2 + 1 = 6, and no other adjacent run reaches it.

Example 2

Input
nums = [-3, -1, -2]
Output
-1
Every run of two or more sums lower, so the best is the single -1 on its own.

The Code

function maxSubArray(nums) {
  let best = nums[0];
  let current = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}
maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]);
Done
Step through maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) call by call

More like this

All dynamic programming examples (20) →