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.

## No comments:

## Post a Comment