Annotated Algorithms: Kadane’s Algorithm

8 min readOct 23, 2020

Understanding the problem

One of the more common problems you might encounter in a software interview involves finding what is commonly referred to as the “maximum sub-array” within a longer array. Take a look at this example here:

We want to write a function that looks at an array and discovers which slice or segment of that array contains a series of numbers that adds up to the largest possible sum.

Since we didn’t specify how long our sub-array needs to be, the maximum sub-array is actually the entire array itself!

You might be thinking, “well duh all of the numbers in an array added together make up the largest sub array, Einstein. What’s the point of looking for a sub-array if we can just add up the whole thing??”

If all instances of this problem were this simple, you’d have a point. Unfortunately, other factors can come into play. What if the function had a second argument to force you into only considering sub-arrays of a given size?

We can’t exploit the loophole of adding up the entire array itself since we have some more parameters to deal with. Let’s pretend we pass in the number 3 as an argument so we only consider subarrays that contain three consecutive numbers.

We can consider a sliding window approach where we look at every possible combination of three consecutive numbers in the array. What would the result of the first window be?

Cool. What if we slide the window over by one index?

Even better! Still, it doesn’t take much time to just look at the array and realize that the largest sum in a window of three numbers would be this:

The window logic to look over each subArray of size 3 might look like something similar to this:

Which would produce the following results in your console:

So far we’ve been able to solve the example problems with ease, but we haven’t yet introduced the main component of this problem that can make things really tricky: the inclusion of negative numbers.

If we continue to include an array size as an argument for our function, we can still utilize the sliding window approach. But what if our responsibility is to determine the largest sum within the array without knowing how large our final sub-array is going to be?

Let’s take a look at one way we could theoretically go about using our window approach, but instead of sliding the window over one index at a time, let’s incrementally expand the window to include more numbers. We’ll start with the first number in the array as its own sub-array:

Easy enough. Let’s add one more number to the window:

Herein lies the problem with negative numbers: simply adding more numbers to the array is no longer guaranteed to give us a larger sum. Things get even more confusing as we iterate deeper into the array. Consider when our loop gets us one index before the -8:

Not only are we worse off by including the -8 in the next iteration….

… but we would have been even better off had we been able to ditch the -3 from earlier in the array that is dragging our sum down

Now we’re really cooking with gas. How do we find the largest sub-array when we have no idea how long the sub-array is supposed to be and there are negative numbers everywhere dragging our sum down??

One possible solution would be to use two pointers and nested for loops to look over every possible combination of array slices using a function like this:

While this does technically work, nesting loops will result in an algorithm that performs in O(N²) or quadratic time at best. For those of you that haven’t gotten to Big O yet, just know that means it’s going to run really slowly. There has to be a better way….

Kadane’s Algorithm

Part 1: maxEndingHere

This algorithm can be a little tricky to wrap your mind around at first, but its implantation actually winds up being very elegant and concise. The first thing we want to do is to borrow from our earlier expanding window concept and declare a variable to keep track of the largest sum in our array as our window expands, but with a twist. Consider the array below:

Let’s start with a window of size one at the first index and use that as the base case for our initial maximum possible sum, which we will track as a comment below the array and save in the variable maxEndingHere

To update the maxEndingHere variable as we continue to expand our window further, we need to consider the following question:

Which of these two operations will result in a bigger number?

1. The next number over in our window?

2. The current maxEndingHere sum + the next number over in our window?

Since the next number over is 5, but the next number over PLUS the maxEndingHere variable is 8, we take 8 as the bigger number, update maxEndingHere, and also update our comment to help us follow along

Let’s keep going. The next number to the right as we expand our window is -9. Which is bigger? -9 alone or -9 PLUS maxEndingHere?

Since -1 is a bigger number than -9, we choose to set that number as the new maxEndingHere

For the next window we finally find an instance where the first option of our two options is larger.

Since the next number over ( 1 ) is larger than maxEndingHere + the next number over ( -1 + 1), we instead choose to set maxEndingHere to be the next number over

Part 2: maxSoFar

Getting an understanding of how maxEndingHere works is the main part of the algorithm, but you probably noticed that the value of maxEndingHere moves up and down a lot as we go. How do we keep track of the largest sum that we’ve encountered so far? You guessed it, another variable!

In addition to another variable to save our maxSoFar, we have another series of questions to help us determine its value.

To illustrate, let’s back up in our loop to the point where our window only contains the first two numbers in our array

Like last time, since -1 is larger than -9, we select that value

But wait, now don’t we have to change maxEndingHere to also equal -1? Don’t you think we should keep track of the previous maxEndingHere value so we don’t lose that biggest value before we update it?

Absolutely. Let’s add two more questions and a variable.

maxSoFar allows us to save the biggest value that we’ve come across so far as we continue to iterate through our loop. Since we know the maxEndingHere value is going to be constantly going up and down, we otherwise wouldn’t be able to recall our previous largest values.

Part 3: Putting it all together

Now that we’ve got the main concepts down, this is what the algorithm would look like in its entirety:

Let’s break it down line by line

First things first, we need values to store in our two variables initially, so we just set their values to be whatever the first number in the array is.

Then we iterate over every number in the array by using a for loop. To determine the value for the next number over (which we will use to determine our maxEndingHere variable), we grab the array at index i