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].