Kadane's Algorithm

Kadane's algorithm finds the contiguous subarray with the largest sum in O(n) time and O(1) space by deciding at each element whether to extend the current run or start fresh.

4 min read Level 2/5 #dsa#arrays#kadane

What you'll learn

Implement Kadane's algorithm and explain the recurrence behind it
Handle the edge case where all elements are negative
Return the actual subarray indices alongside the maximum sum

Given [-2, 1, -3, 4, -1, 2, 1, -5, 4], what contiguous subarray has the largest sum? The brute-force answer is to try every pair (i, j) in O(n²). Kadane’s insight reduces this to a single linear scan.

The Intuition

At every index i, the maximum subarray ending exactly at i is either:

just nums[i] alone (start a new run), or
nums[i] extended from the best run ending at i-1.

Pick whichever is larger. Track the global max as you go.

Implementation

function maxSubarraySum(nums) {
  let current = nums[0];
  let best = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Extend current run or start fresh
    current = Math.max(nums[i], current + nums[i]);
    if (current > best) best = current;
  }
  return best;
}

// Walk-through: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// i=1: current=max(1, -2+1)=1,   best=1
// i=2: current=max(-3,1-3)=-2,   best=1
// i=3: current=max(4,-2+4)=4,    best=4
// i=4: current=max(-1,4-1)=3,    best=4
// i=5: current=max(2,3+2)=5,     best=5
// i=6: current=max(1,5+1)=6,     best=6
// i=7: current=max(-5,6-5)=1,    best=6
// i=8: current=max(4,1+4)=5,     best=6
console.log(maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

Edge Case: All Negatives

If every element is negative the maximum subarray is a single element — the largest (least negative) one. The implementation above handles this correctly because current starts at nums[0] rather than 0, so it never considers the empty subarray.

console.log(maxSubarraySum([-5, -1, -8, -3])); // -1 (single element)

Returning the Actual Indices

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

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > current + nums[i]) {
      current = nums[i];
      tempStart = i;
    } else {
      current = current + nums[i];
    }
    if (current > best) {
      best = current;
      start = tempStart;
      end = i;
    }
  }
  return { sum: best, start, end };
}

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

Complexity

Metric	Value
Time	O(n)
Space	O(1)
Passes	1
Handles all-negative	Yes (returns single element)

Up Next

The Dutch National Flag problem also runs in O(n)/O(1) — it partitions an array into three groups in a single pass using three pointers instead of two.

Dutch National Flag →