Kadane’s Algorithm

Kadane’s Algorithm is an algorithm that solves a question called the Maximum Subarray Problem. It’s a very simple algorithm at first glance, but when you start digging into it, it becomes a lot more complicated.

In computer science, the maximum sum subarray problem is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1…n] of numbers. Formally, the task is to find indices i and j with 1 < i < j < n, such that the sum is as large as possible.

— Wikipedia’s definition of Maximum Subarray Problem

In other words, it’s when you’re given an array of integer values and want to find the greatest sum that you can generate by summing numbers in some subarray in the input array.

You would think it would be an easy solution but the challenge comes when we start introducing negative numbers. Because it’s going to completely ruin a potential greatest sum.

Walkthrough

First, we need to initialize our maxEndingHere and maxSoFar variables to the first value in the array.

function kadanesAlgo(array) {
  maxEndingHere = array[0]
  maxSoFar = array[0]
}

The simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array (maxEndingHere). And keep track of maximum sum contiguous segment among all positive segments (maxSoFar).

Then we could start iterating through the rest of the array starting at index 1 and assigning a variable to it.

function kadanesAlgo(array) {
  maxEndingHere = array[0]
  maxSoFar = array[0]
  for(let i = 1; i < array.length; i++) {
    const num = array[i];   
  }
}

Now we need to update our maxEndingHere and maxSoFar variable using a formula.

function kadanesAlgo(array) {
  maxEndingHere = array[0]
  maxSoFar = array[0]
  for(let i = 1; i < array.length; i++) {
    const num = array[i];
    maxEndingHere = Math.max(num, maxEndingHere + num);
    maxSoFar = Math.max(maxSoFar, maxEndingHere)
  }
}

We need to Update maxEndingHere by taking the maximum value of either, the number alone (num) or the number plus the previous value of maxEndingHere (maxEndingHere + num)

Similarly we need to update maxSoFar, by updating it to the maximum value of maxSoFar and the current value of maxEndingHere. It’s important to update maxSoFar after we’ve updated maxEndingHere.

function kadanesAlgo(array) {
  maxEndingHere = array[0]
  maxSoFar = array[0]
  for(let i = 1; i < array.length; i++) {
    const num = array[i];
    maxEndingHere = Math.max(num, maxEndingHere + num);
    maxSoFar = Math.max(maxSoFar, maxEndingHere)
  }
  
  return maxSoFar
}

Then we could iterate through the rest of the array and just return maxSoFar. At this point, we have traversed the entire array, we’ve calculated and updated the values for all the maxEndHere and values for all maxSoFar. However we only kept the one value of maxSoFar, which is the answer.