Kadane's Algorithm

Kadane's Algorithm – Efficient Maximum Subarray Sum
 The Problem

Imagine you're playing a game where you score positive or negative points each round.
You want to find the maximum total score you can get by choosing a sequence of consecutive rounds.

This is known as the:

Maximum Subarray Problem

Naive (Brute Force) Solution

You could solve it by checking all possible subarrays and summing each one.
Example:

[2, -3, 6]

All possible consecutive subarrays:

Subarray Sum
[2] 2
[2, -3] -1
[2, -3, 6] 5
[-3] -3
[-3, 6] 3
[6] 6 ✅

The maximum sum is 6.

But this method becomes very slow for long arrays → O(n²) time complexity.

Kadane’s Algorithm (Efficient O(n) Solution)

Kadane’s Algorithm solves this problem in linear time → O(n)
It's based on Dynamic Programming, but it’s extremely space-efficient (uses only two variables).

Key Concepts

We use two variables:

Variable Purpose
currentSum The running sum of the current subarray (candidate for max subarray)
maxSum The best (maximum) sum found so far

We iterate through the array once, updating these two values at each step.

Algorithm Logic

At each item x in the array:

Add x to currentSum → means we’re trying to extend the current subarray.

If currentSum > maxSum, update maxSum.

If currentSum < 0, reset currentSum to 0 → we start fresh, because a negative sum will hurt any future subarray.

JavaScript Implementation

function maxSubArray(arr) {
  let currentSum = 0;
  let maxSum = -Infinity; // works even if all values are negative
  for (let x of arr) {
    currentSum += x;
    if (currentSum > maxSum) {
      maxSum = currentSum;
    }
    if (currentSum < 0) {
      currentSum = 0;
    }
  }
  return maxSum;
}
Step-by-step Example

Let’s walk through the array:

const arr = [2, -1, 3, -4, 5, -2, 2];
Index Value currentSum Before currentSum After maxSum
0 2 0 2 2
1 -1 2 1 2
2 3 1 4 4 ✅
3 -4 4 0 (reset) 4
4 5 0 5 5 ✅
5 -2 5 3 5
6 2 3 5 5

Final result: maxSum = 5

Special Case: All Negative Numbers

If the array has only negative numbers, Kadane’s algorithm still works because we initialize:

let maxSum = -Infinity;

So it will still return the maximum negative value instead of returning 0.

 Summary

Kadane’s algorithm solves the Maximum Subarray Problem in O(n) time and O(1) space.

It uses only two variables: currentSum and maxSum.

You reset currentSum to 0 when it becomes negative, because any negative prefix will reduce your future total.

Kadane’s Algorithm is a clean, fast, and optimal way to find the largest sum of a contiguous subarray.