jsschools

Kadane's Algorithm

Finds the maximum sum contiguous subarray in O(n) time and O(1) space by tracking the maximum sum ending at each position.

Spec ↗

Syntax

kadane(arr)

Parameters

NameTypeRequiredDescription
arr number[] Yes Array of numbers (may include negatives). Must be non-empty.

Returns

{ maxSum: number, start: number, end: number } — Maximum subarray sum with the inclusive start and end indices.

Examples

function kadane(arr) {
  let maxSum = arr[0], curSum = arr[0];
  let start = 0, end = 0, tempStart = 0;

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > curSum + arr[i]) {
      curSum = arr[i];
      tempStart = i;
    } else {
      curSum += arr[i];
    }
    if (curSum > maxSum) {
      maxSum = curSum;
      start = tempStart;
      end = i;
    }
  }
  return { maxSum, start, end };
}

console.log(kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
Output 
{ maxSum: 6, start: 3, end: 6 }

// All negative numbers: returns the least negative element
function kadane(arr) {
  let maxSum = arr[0], curSum = arr[0];
  for (let i = 1; i < arr.length; i++) {
    curSum = Math.max(arr[i], curSum + arr[i]);
    maxSum = Math.max(maxSum, curSum);
  }
  return maxSum;
}

console.log(kadane([-3, -1, -2]));
Output 
-1

Notes

| Case | Time | Space | |---------|------|-------| | Best | O(n) | O(1) | | Average | O(n) | O(1) | | Worst | O(n) | O(1) | Kadane's algorithm uses the recurrence: `maxEndingHere[i] = max(arr[i], maxEndingHere[i-1] + arr[i])`. The greedy choice is: extend the current subarray if it increases the sum, otherwise start a new subarray at the current element. For circular arrays (maximum subarray wrapping around), the answer is max(kadane(arr), totalSum - kadane(-arr)), handling the case where all elements are negative by returning max(arr).

See also