Programmers Army

Kadane’s Algorithm

The main idea of this algorithm is to efficiently get the maximum sum in any subarray.

Remember the subarray is obtained by deleting some elements in the beginning (possibly zero) and deleting some elements from the end (possibly zero).

Let’s start with the need of this algorithm.

As you know at first the problem seems to be doable in O(N^2) complexity where N is the size of the array. But is this complexity feasible?

We won’t be discussing the naïve approach since that is too obvious and complexity issues.

So, we need to look for something in O(N).

Let’s do the following and observe what is happening.

1. Keep two variables, one storing our answer and another one is a temp variable.

2. Start iterating over the array.

3. Add the value a[i] to the temp. i is the position we are currently at.

4. If the value of temp goes negative make it zero or else make our answer=max(temp,answer);

5. Repeat this process till the end.

And now what we have is our answer stored in ans variable.

How did it work?

Well, it is not hard to convince ourselves that whenever we encounter an element which is highly negative we won’t be taking into account because it will worsen up the sum. And that makes us to believe that until and unless we find an element which makes the sum negative we will keep adding, every time we see a positive sum going ahead that simply means its an sum of subarray of any arbitrary length to the left. Since every check is done on an arbitrary length going back which is not directly visible here but its actually happening, So you’ll later get to know in dynamic programming that it’s a similar way of approaching a dynamic programming problem.

Implementation:

Dry run on a sample test case:

Let A={4,-3,2,-10,2,1,-1,3}

Assume 1 based indexing:

Initially, temp=0 and ans=INT_MIN

After 1^st iteration: temp=4, ans=4.

After 2^nd iteration: temp=1, ans=4.

After 3^rd iteration: temp=3, ans=4.

After 4^th iteration: temp=0, ans=4.

After 5^th iteration: temp=2, ans=4.

After 6^th iteration: temp=3, ans=4.

After 7^th iteration: temp=2, ans=4.