1.6 Kadane's Algorithm

Demo: Maximum Subarray — LC 53 (Medium)

Statement (Demo): Given an integer array nums, find the contiguous subarray with the largest sum and return that sum. Example: [-2,1,-3,4,-1,2,1,-5,4] → 6 | ⚡ n ≤ 10⁵, -10⁴ ≤ nums[i] ≤ 10⁴

Approach: At each index decide: if the running sum still helps, extend it; otherwise start a new subarray here. Keep the global best separately.

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]); // start fresh vs extend
    best = Math.max(best, cur);
  }
  return best;
}

Complexity: Time O(n), Space O(1)