Maximum SubarrayMedium

Given an array of integers (can include negatives), find the contiguous subarray with the largest sum, and return that sum.

Examples

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] → Output: 6, from [4,-1,2,1]

Approach

Checking every possible subarray is O(n²). Kadane's Algorithm (see dsa/kadane.html for the deeper walkthrough) gets it in one pass by making a local decision at each index: is it better to extend the running subarray, or abandon it and start fresh at the current element? Track the best sum ending exactly at the current index, and separately the best sum seen anywhere so far.

Complexity — best & worst case

Brute force — time O(n²)

Optimal (Kadane's) — time O(n), best and worst case are the same — always one full pass

Optimal (Kadane's) — space O(1)

Code

// Given an array of integers (can include negatives), find the
// contiguous subarray with the largest sum, and return that sum.

// --- Brute force: check every possible subarray ---
function maxSubArrayBrute(nums) {
  let max = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      max = Math.max(max, sum);
    }
  }
  return max;
}

// --- Optimal: Kadane's Algorithm, one pass (see dsa/kadane.html for the
// deeper walkthrough of WHY this works) ---
function maxSubArray(nums) {
  let maxEndingHere = nums[0];
  let maxSoFar = nums[0];

  for (let i = 1; i < nums.length; i++) {
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

// --- Example Usage ---
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6, from [4,-1,2,1]
console.log(maxSubArrayBrute([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log(maxSubArray([-1])); // -1
console.log(maxSubArray([5, 4, -1, 7, 8])); // 23, whole array