Kadane's Algorithm

#programming #algorithms

Problem :

Find the maximum subarray sum, given an array

Solution

1.

Naive approach to use brute-force $O(n^2)$

2. Kadane's Algorithm

A dp like solution, you remember the maximum subarray sum ending at the index before your current index, and you decide to start a new subarray at the current index or start afresh depending the cases.

int res = arr[0]; // overall sol
int maxEnding = arr[0] // max ending at index 0 is that fellow
for (int i = 0; i < arr.size(); i++)
{
	maxEnding = max(arr[i], maxEnding + arr[i]);
	res = max(maxEnding, res);
}
cout << res << endl;

If the inclusion of current element makes the sum smaller than the element itself, we start afresh. Otherwise we extend.

The answer is the max of {cpp}maxEnding across all indexes.