Daily Algorithms: #2 (Kadane Algorithm)

How to find the subarray with the largest sum in a given array

This is a repeated common question one might encounter while solving CP problems. Kadane algorithm is used to solve this problem. Before we reach into the implementation, we should try to solve this with a bruteforce approach

1. Naive approach:

The most basic thing we can do is, start with each index of the array and keep a track of sums. Then, we compare the sums that we have obtained and return the largest subarray.

1. Generate a list of all subarrays.
2. Generate sums for all subarrays.
3. Return subarray with largest sum

The time complexity for this approach is O(n²). This is a very inefficient solution.

Here’s the thing before starting to learn kadane algorithm: Do not try to overcomplicate it. Most examples and websites out there will try to lead you astray, by showing you rote-learned examples, which make use of the same variable names over and over again. Let’s try to understand kadane algorith conceptually.

I will ask you two questions — basic arithmetic questions.

Q. True or false: -1+2 > 2?

If you can answer this question, then you can understand kadane algorithm!

Let’s outline the steps for the algorithm first.

1. Start with array.
2. Let us consider that there is a subarray, whose sum is equal to sum_here, and starts at some index “start” and ends at index “end” in the array.

How would we find such an array?

Well, the basic nature of kadane algorithm is improved for mixed case: when both positive and negative numbers are included. Let’s take an example for now. I will list an array of numbers, and you need to find the subarray with the largest sum!

[-1, 1, 2, 3, -4]

It’s 6, from subarray [1, 2, 3]. Easy, right?

Well, kadane algorithm works the same way. When we start out, we assume that the subarray starts from the beginning of given array and current sum is 0. For each element in the array, we then check the following:

1. If the current element, added to the current sum, yields a value which is actually lesser than the element itself, then there’s no point in considering the previous sum. We might as well start the largest subarray from this element onwards and continue in the provided fashion.
2. If the current element, added to the current sum, yields a value greater than the item itself, then we should cross check it with the largest sum that we have found so far. If the sum exceeds the largest sum, then the subarray starts somewhere and ends at this element. Otherwise, we just continue.

What this means is that, if adding a sum to the given index’s element is lesser than the element, then it must mean that the sum is negative, and the item is positive or negative, but it is larger than the current sum. Since we are after the largest sum, we can discard our current progress and continue!

Illustration of problem: Credits (Geeksforgeeks)

In the above figure, we can see, starting with -2, the largest sum is -2. If we add -3 to the sum, then we get -5, which is smaller than -3, so we discard -2 and start our subarray from -3. Then we add 4, which gives us value 1, which is still, smaller than 4. So we discard -3 and start subarray from 4. Then we add -1. We get 3, which is larger than -1, so we check the sum(3) against the largest sum recorded so far, which is 1. As 3 > 1, we mark this as the end of the subarray. So far, the maximal sum subarray contains [4, -1]. Then we add -2. As 3 + -2 = 1, which is greater than -2, but lower than max recorded sum(3), we will not mark our array to end here. So far, the maximal subarray contains [4, -1]. Then we reach 1. Still we won’t mark the end of the subarray. Then we reach 5. At this point, the sum becomes 7, which is greater than 3. So our maximal subarray ends at this point so far. Then we consider -3. Adding it to 7 gives us 4, which is lesser than the sum recorded so far.

Manual walkthroughs can be tough. Let’s look at a gist:

Happy coding!