Kadane's Algorithm

Kadane's algorithm finds the highest-summing run of neighbouring numbers — the maximum subarray — in a single left-to-right pass. It keeps a running total of the current run and, the moment that total turns negative, throws it away and starts fresh, because a negative prefix can only drag down whatever comes next.

The one decision per element

At each element x you make a single choice: extend the current run by adding x, or restart a fresh run at x alone. You extend when the running sum so far is positive (it helps) and restart when it's negative (it hurts). Both cases collapse into one line: cur = max(x, cur + x), then best = max(best, cur).

Worked trace

Run it on [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Track cur (best run ending at each index) and best (best seen so far):

array:  -2   1  -3   4  -1   2   1  -5   4
cur:    -2   1  -2   4   3   5   6   1   5
best:   -2   1   1   4   4   5   6   6   6

The answer is 6, the subarray [4, -1, 2, 1]. Watch index 2: cur goes to -2, and at index 3 the running sum -2 + 4 = 2 is worse than starting fresh at 4, so Kadane restarts — exactly where the winning run begins.

function maxSubArray(nums) {
  let cur = nums[0], best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]); // extend, or restart at nums[i]
    best = Math.max(best, cur);             // record the best seen
  }
  return best;
}