53. Maximum Subarray

Find the contiguous subarray with the largest sum and return its sum.

At each index, either extend the current subarray or start fresh, whichever is larger. A negative running sum only hurts, so drop it.

1function maxSubArray(nums: number[]): number {
2  let cur = nums[0], best = nums[0];
3  for (let i = 1; i < nums.length; i++) {
4    cur = Math.max(nums[i], cur + nums[i]);
5    best = Math.max(best, cur);
6  }
7  return best;
8}

cur = -2best = -2

nums

-2

-3

-1

-5

cur = best = nums[0] = -2.

1 / 0

Space: play/pause · ←/→: step