# Annotated Algorithms: Kadane’s Algorithm

# 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 overin our window?

2. The current

maxEndingHeresum + thenext number overin 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*

Remember how we determine the value of **maxEndingHere**? We decide which number is larger:

The **next number over** — OR — the **next number over + maxEndingHere**

Finally, we use the **maxEndingHere** value to determine the largest value between **maxEndingHere** and **maxSoFar**

Lastly, we simply return whatever the value is for **maxSoFar** after we’ve broken out of our *for* loop!