Maximum Subarray – Kadane

A You’re given an integer array of length n and your required to compute the sum of a k contiguous elements that have the maximum sum.
A brute force solution would be . So we present Kadane’s algorithm which solves the problem in an slick subrotine.
The idea is simple. First, take a look at the pseudo-code:

KADANE(array, len)
	sum = 0
	maxSum = -
	for x = 0 to len
		sum += array[x]
		maxSum = MAX(sum, maxSum)
		if(sum < 0)
			sum = 0
	return maxSum

We keep adding up elements until the sum changes sign, then, we reset the sum.
The algorithm has a key observation, that whenever a contiguous chunk of the array gives negative sum, it’s no longer of use:

• Adding up more elements to this chunk is not a good choice. We’d better take these new elements in a new chunk so that we could benefit most from them
• There’s some “barrier” that made this chunk change sign — a very large negative element(s) at which we reset sum –. No maximum subarray would be crossing that barrier.

Why is this a Dynamic Programming algorithm?
The maximum subarray ending at each position is calculated from a related but smaller subproblem which is the maximum subarray ending at the previous position.

An implementation in C++:

#include <iostream>
#include <climits>
using namespace std;

#define MAX(X, Y) (X > Y) ? X : Y
#define POS(X) (X > 0) ? X : 0

#define N 11

int arr[N] = { 1, -6, 2, -1, 4, -1, 2, 1 };

int maxSum = INT_MIN;

int kadane(int* row, int len) {
	int x, sum, maxSum = INT_MIN;
	for (sum = POS(row[0]), x = 0; x < N; ++x, sum = POS(sum + row[x]))
		maxSum = MAX(sum, maxSum);
	return maxSum;
}

int main() {
	cout << kadane(arr, N) << endl;
	return 0;
}