Kadane's Algorithm

Kadane's algorithm finds the contiguous subarray with the largest sum in O(n) time. It is a textbook example of turning a seemingly quadratic problem into a linear one by asking the right question at each step.

Problem Statement

Given an integer array nums (which may contain negative numbers), find the contiguous subarray that has the largest sum and return that sum.

Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → answer is 6 (subarray [4,-1,2,1]).

Brute Force — O(n³) → O(n²)

The most naive approach enumerates all pairs (l, r) and recomputes the sum from scratch — O(n³). A minor improvement computes the sum incrementally as r grows — O(n²). Both are too slow for large inputs.

// O(n³) — don't use this
function maxSubarrayN3(nums) {
  let max = -Infinity;
  for (let l = 0; l < nums.length; l++) {
    for (let r = l; r < nums.length; r++) {
      let sum = 0;
      for (let k = l; k <= r; k++) sum += nums[k];
      max = Math.max(max, sum);
    }
  }
  return max;
}

// O(n²) — incremental sum
function maxSubarrayN2(nums) {
  let max = -Infinity;
  for (let l = 0; l < nums.length; l++) {
    let sum = 0;
    for (let r = l; r < nums.length; r++) {
      sum += nums[r];
      max = Math.max(max, sum);
    }
  }
  return max;
}

Kadane's Algorithm — O(n)

The core insight: at each position i, you face one binary choice —

Extend the previous subarray: add nums[i] to currentSum.
Restart a new subarray: begin fresh at nums[i].

The better choice is whichever is larger: Math.max(nums[i], currentSum + nums[i]), which simplifies to: if currentSum is negative, restart (a negative prefix can only hurt).

// LeetCode 53 — Maximum Subarray
function maxSubarray(nums) {
  let currentSum = nums[0];
  let maxSum     = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Extend or restart?
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum     = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

console.log(maxSubarray([-2,1,-3,4,-1,2,1,-5,4])); // 6
console.log(maxSubarray([1]));                       // 1
console.log(maxSubarray([5,4,-1,7,8]));              // 23

Note

Time: O(n). Space: O(1). The algorithm makes exactly one pass and maintains only two variables. It is also a special case of dynamic programming: dp[i] = max(nums[i], dp[i-1] + nums[i]).

Handling All-Negative Arrays

When all numbers are negative, the maximum subarray is the single least-negative element. The implementation above handles this automatically by initialising both currentSum and maxSum to nums[0] rather than 0 or -Infinity.

If you initialise to 0, you implicitly allow the empty subarray — return 0 when all elements are negative — which is wrong if the problem requires a non-empty subarray.

// All negative — must return the largest (least negative) element
console.log(maxSubarray([-3, -1, -2])); // -1  ✅

// Wrong version — initialise to 0
function maxSubarrayWrong(nums) {
  let current = 0, best = 0;
  for (const n of nums) {
    current = Math.max(0, current + n);
    best = Math.max(best, current);
  }
  return best; // returns 0 for all-negative — WRONG if empty not allowed
}

Warning

Always initialise currentSum and maxSum to nums[0], not 0. Starting at 0 silently allows the empty subarray as a candidate.

Return Indices, Not Just the Sum

Interviewers sometimes ask you to return the start and end indices of the best subarray, not just its sum. Track when you restart and when you update the best.

function maxSubarrayWithIndices(nums) {
  let currentSum = nums[0];
  let maxSum     = nums[0];
  let start = 0, tempStart = 0;
  let end   = 0;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > currentSum + nums[i]) {
      // Restart — new subarray begins here
      currentSum = nums[i];
      tempStart  = i;
    } else {
      currentSum += nums[i];
    }

    if (currentSum > maxSum) {
      maxSum = currentSum;
      start  = tempStart;
      end    = i;
    }
  }
  return { maxSum, start, end, subarray: nums.slice(start, end + 1) };
}

const res = maxSubarrayWithIndices([-2,1,-3,4,-1,2,1,-5,4]);
console.log(res);
// { maxSum: 6, start: 3, end: 6, subarray: [4,-1,2,1] }

Circular Array Variant — LeetCode 918

In a circular array, the subarray can wrap around. There are two cases:

Normal: the best subarray does not wrap — use standard Kadane's.
Wrapping: the best subarray wraps — equivalent to removing the minimum subarray from the middle, leaving two segments at the ends.

For case 2: wrappingMax = totalSum - minSubarray.

The answer is max(normalMax, wrappingMax). Edge case: if all elements are negative, wrappingMax = 0 (empty removal), but the array is non-empty, so return normalMax.

function maxSubarrayCircular(nums) {
  let totalSum   = 0;
  let maxSum     = nums[0], currentMax = nums[0];
  let minSum     = nums[0], currentMin = nums[0];

  for (let i = 1; i < nums.length; i++) {
    currentMax = Math.max(nums[i], currentMax + nums[i]);
    maxSum     = Math.max(maxSum, currentMax);

    currentMin = Math.min(nums[i], currentMin + nums[i]);
    minSum     = Math.min(minSum, currentMin);

    totalSum  += nums[i];
  }
  totalSum += nums[0]; // we skipped index 0 in the loop

  // If all elements are negative, maxSum holds the answer (avoid empty wrap)
  if (maxSum < 0) return maxSum;
  return Math.max(maxSum, totalSum - minSum);
}

console.log(maxSubarrayCircular([1,-2,3,-2]));  // 3
console.log(maxSubarrayCircular([5,-3,5]));      // 10
console.log(maxSubarrayCircular([-3,-2,-3]));    // -2

Complexity Summary

Variant	Time	Space
Basic maximum subarray	O(n)	O(1)
With index tracking	O(n)	O(1)
Circular array	O(n)	O(1)
Brute force O(n²)	O(n²)	O(1)

Practice Problems

LeetCode 53 — Maximum Subarray (classic Kadane)
LeetCode 918 — Maximum Sum Circular Subarray
LeetCode 152 — Maximum Product Subarray (track max and min)
LeetCode 1749 — Maximum Absolute Sum of Any Subarray
LeetCode 363 — Max Sum of Rectangle No Larger Than K (Kadane + sorted set)