Maximum Subarray Sum: Kadanes Algorithm (Dynamic Programming)

Problem: We have to find the maximum subarray sum.

Eg: Lets consider this array ⇒ -10, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, -4, the answer for maximum subarray sum is 19. (1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1)

Solution ⇒ Naive approach, brute-force. Generate all the arrays and get the maximum sum.

From this, we can generate subarrays like,

-10

-10, 5

-10, 5, 9

-10, 5, 9, 1

-10, 5, 9, 1 , 3

...

...

5

5, 9

5, 9, 1

5, 9, 1, 3

5, 9, 1, 3, 2

..

...

We can generate all the subarrays and take the maximum sum, in that case, our code will look like

// n*n solution
#include <vector>
using namespace std;

int notKadanesAlgorithm(vector<int> array) {
	int n = array.size();
	vector<int> sum;
	int res = INT_MIN;

	//Cumulative Sum
	sum.push_back(array[0]);
	for(int i = 1; i < n; i++)sum.push_back(sum[i-1] + array[i]);

	// Generate every pair and take maximum.
	for(int i = 0; i < n; i++) {
		for(int j = i; j < n; j++  ) {
			res = max(res, sum[j]-sum[i - 1]);
		}
	}
  return res;
}

But this has a complexity of O(n^2) we can reduce it to O(n) if we use Kadane's algorithm. Which uses dynamic programming. While traversing the array, we can keep track of what was the maximum number, if the array was ended here.

for example, if our array is -1, 2, 3, -4, we can generate another array which ith position will hold the maximum value if the array was ended here. We'll get -1, 2, 5, 1

. Let me explain how.

In any place, we have either 2 choices. Either we can add the current array item in our sum, or we can start a new array from here.

When i = 0, our maxEndingHere[0] = -1 ⇒ we don't have any option but to take the first element.

then i = 1, we get 2 as the current value of the array. Now we have 2 choices:

1. We can consider the subarray ends here (index 1, having value 2). The subarray is -1, 2, in that case, we can get our maximum subarray sum -1+2=-1
2. We can consider a new subarray starting from here. The subarray is 2, resulting in maximum subarray sum = 2

as the second option results in maximum value, we will go with it. So, maxEndingHere[1] = 2

After that when i = 2, we get the maximum subarray sum if we take 3, is 5, or we can start a subarray from here, which will give us 3. So our maxEndingHere[2] = 5

and finally, in the same procedure, we can get maxEndingHere[3] = 1( max( (5 -4), -4)))

So our resulted maxEndingHere array is ⇒ -1, 2, 5, 1

we can find the maximum number of this array, which is the result, for this example, 5.

Our code will look like this:

#include <vector>
using namespace std;

int kadanesAlgorithm(vector<int> array) {
	vector<int>maxEndHere;
	if(array.size()>0)maxEndHere.push_back(array[0]);

	for(int i = 1; i < array.size(); i++){
		int here = max(maxEndHere[i-1]+array[i], array[i]);
		maxEndHere.push_back(	here );
	}

// Finding the maximum array in this vector
	return *max_element(maxEndHere.begin(), maxEndHere.end());
}

Now it runs on O(n) but space complexity is still O(n) which we can reduce to O(1) but not store the whole array into maxEndHere. We can just declare an integer and keep the maximum value in it while traversing the array. But this task is for you to do. 😇