Kadane’s algorithm

If you have seen interview questions like find the maximum sum in an array using any contiguous sub-arrays in it then you should read further.

We have discussed a few dynamic programming questions on this website. This post talks about yet another one (arguably). Let’s take an example – in the array {-2, -3, 4, -1, -2, 1, 5, -3}, what is the maximum sum that you can obtain by summing up any contiguous elements in it? Well, you can compare each element one by one and build an O(n*n) solution to do that. But can we do better? Let’s see what Mr. Kadane proposed.

For every i, let’s try to calculate the maximum sum possible till that i.

Array = {-2, -3, 4, -1, -2, 1, 5, -3}; i will go from 0 to 7. Let’s keep two variables:
sum_at_i = 0
max_sum = 0

At i = 0;
sum_at_i = sum_at_i + array[i] = -2
Since sum_at_i < 0, we re-initialize:
sum_at_i = 0
max_sum = 0

At i = 1;
sum_at_i = sum_at_i + array[i] = -3
Since sum_at_i < 0, we re-initialize:
sum_at_i = 0
max_sum = 0

At i = 2;
sum_at_i = sum_at_i + array[i] = 4
Since sum_at_i > 0 and sum_at_i > max_sum; we make:
sum_at_i = 4
max_sum = 4

At i = 3;
sum_at_i = sum_at_i + array[i] = 4 – 1 = 3
Since sum_at_i > 0 but sum_at_i < max_sum; we don’t change max_sum:
sum_at_i = 3
max_sum = 4

At i = 4;
sum_at_i = sum_at_i + array[i] = 3 – 2 = 1
Since sum_at_i > 0 but sum_at_i < max_sum; we don’t change max_sum:
sum_at_i = 1
max_sum = 4

At i = 5;
sum_at_i = sum_at_i + array[i] = 1 + 1 = 2
Since sum_at_i > 0 but sum_at_i < max_sum; we don’t change max_sum:
sum_at_i = 2
max_sum = 4

At i = 6;
sum_at_i = sum_at_i + array[i] = 2 + 5 = 7
Since sum_at_i > 0 and sum_at_i > max_sum; we make:
sum_at_i = 7
max_sum = 7

At i = 7;
sum_at_i = sum_at_i + array[i] = 7 – 3 = 4
Since sum_at_i > 0 but sum_at_i < max_sum; we don’t change max_sum:
sum_at_i = 4
max_sum = 7

And there we go! Our answer is 7. (But can you also find the indices of the sub-array?)

You can find the corresponding C++ code for the above algorithm HERE.

Now that you have found the maximum sum, can you also find the minimum sum? Give it a try.

References:

1. GeeksforGeeks 2017. “Largest Sum Contiguous Subarray”. https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/. [Online; accessed 27-March-2018].
2. Kartik Kukreja 2013. “Everything Under The Sun”. https://kartikkukreja.wordpress.com/2013/06/17/kadanes-algorithm/. [Online; accessed 27-March-2018].