## Pages

I have already shown a solution to the maximum subarray problem, based on an algorithm that follows the divide and conquer recipe. Here I give a couple of C++11 implementations based on the asyntotically better algorithm devised by Professor Kadane in the dynamic programming spirit.

The basic idea is keeping memory of the higher sum already reached and increasing a current sum. If the current sum gets higher than the historical one, also that one is increased.

This is a first version, that calculates just the sum:
typedef std::vector<int> Vector;

int maxSubAr(const Vector& data)
{
int sum = 0;
int sumTmp = 0;

for(unsigned i = 0; i < data.size(); ++i)
{
if(int value = sumTmp + data[i] > 0) // 1
sumTmp = value;
else
sumTmp = 0;

if(sumTmp > sum) // 2
sum = sumTmp;
}

return sum;
}
1. Add the current element value to the temporary sum. If this leads to a positive number, this will be the new temporary sum, otherwise I reset it.
2. If the temporary sum is bigger than the previously saved sum, I save this new value.

And that's it. Incredibly simple and effective.

Things get a bit more complicated when we want to get also the first-last index of the subsequence:
typedef std::array<int, 3> Info;
typedef std::vector<int> Vector;

Info maxSubArray(const Vector& data)
{
int left = 0;
int right = 0;
int sum = 0;

int leftTmp = 0;
int sumTmp = 0;

for(unsigned i = 0; i < data.size(); ++i)
{
int value = sumTmp + data[i];
if(value > 0)
{
if(sumTmp == 0) // 1
leftTmp = i;
sumTmp = value;
}
else
sumTmp = 0;

if(sumTmp > sum) // 2
{
left = leftTmp;
right = i;
sum = sumTmp;
}
}

return {{ left, right, sum }};
}
1. If I am at the beginning of the sequence, or if I have just reset the temporary sum, the current value is at the tentative first element of the subsequence.
2. When I see that the current sum is bigger than the one already discovered, I adjust also the left/right indexes.

Full C++11 code is on github, with a few GoogleTest test as a bonus.