Max subsequence

[n4nature]

Here's the code that returns maximum sum of a subsequence from a given array. This is according to "Programming Pearls" by Jon Bentley. I have come up with an example for which this program won't work. And here's that example:

{ -10, 11, 10, -10, 2, 3, -6, 1 }

Max subsequence sum above is 21. 2nd and 3rd elements.

But the program returns 16. It sums 2nd through 6th elements and returns. Why would the writer explain something with such depth, only to give a program that doesn't work in all instances? So I am thinking there is something wrong with my understanding of the program. Could you tell if it's the program, or my understanding? Thanks!

int MaxSum(int lo, int hi, int* arr)
{
	if (lo > hi)
	{
		return 0;
	}
	if (lo == hi)
	{
		return arr[lo];
	}

	int mid = (lo + hi) / 2;

	int maxLeft = 0;
	int maxRight = 0;

	int sum = 0;

	for (int i = lo; i <= mid; ++i)
	{
		sum += arr[i];
		if (sum > maxLeft)
		{
			maxLeft = sum;
		}
	}

	sum = 0;
	for (int i = mid+1; i <= hi; ++i)
	{
		sum += arr[i];
		if (sum > maxRight)
		{
			maxRight = sum;
		}
	}

	int MaxCrossing = maxLeft + maxRight;

	int maxInA = MaxSum(0, mid, arr);
	int maxInB = MaxSum(mid + 1, hi, arr);

	return max(MaxCrossing, maxInA, maxInB);
}

[Duthomhas]

Given your sequence

{ -10, 11, 10, -10, 2, 3, -6, 1 }

Then the maximum sum subsequence is technically 27:

sum of { 11, 10, 2, 3, 1 }

If you are looking for a contiguous subsequence, then the maximum is 21.


As for the code, I'm not too impressed. A lot of times code gets into books that hasn't been either reviewed, or, shockingly, even compiled.

Whoever wrote this piece wasn't thinking very clearly. It tries to do a couple things the wrong way.


For the problem at hand, finding the maximum continuous subsequence sum, the answer is straightforward, requiring no recursion or 'divide and conquer' style partitioning.

Just discount negative numbers, and find the largest sum of the remaining sequences. If only negative numbers are present, take the largest one (the one with the least magnitude).

int max_sum( int* arr, int n )
{
  // The initial max number will be the first available number, if any.
  // (Because no maximum can be less than any single value in the array.)
  int max = 0;
  if ((arr) && (n)) max = arr[0];

  // Our loop is a special nested loop.
  // Outer loop: while there are elements still in the array...
  int i = 0;
  while (i < n)
  {
    // First inner loop: find the largest individual value in 
    // a contiguous sequence of negative values.
    for (; (i < n) && (arr[i] < 0); ++i)
    {
      if (arr[i] > max) max = arr[i];
    }
    
    // Second inner loop: sum a contiguous sequence of
    // positive values.
    if ((i < n) && (arr[i] >= 0))
    {
      int sum = 0;
      for (; (i < n) && (arr[i] >= 0); ++i)
      {
        sum += arr[i];
      }
      // (Is the sum the new max?)
      if (sum > max) max = sum;
    }
  }
  
  return max;
}

Notice how we must be careful to not overrun the array's bounds at every step. (Because the special two-inner-loop nature of the problem -- it is possible that the first inner loop exhausted the elements in the array, so the second inner loop cannot be allowed to try without testing that there are elements to play with.)

Here's a main to test it out.

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

int main()
{
  vector <int> sequence;
  cout << "Enter subsequence: ";
  {
    string s;
    getline( cin, s );
    istringstream ss( s );
    int n;
    while (ss >> n) 
    {
      sequence.push_back( n );
      ss.get();
    }
  }
  cout << "max sum = " << max_sum( sequence.data(), sequence.size() ) << "\n";
}

Enter subsequence: -10, 11, 10, -10, 2, 3, -6, 1
max sum = 21

Enter subsequence: -10 -9 -6 -100
max sum = -6

Enter subsequence:
0

Enter subsequence: -1 2 3 -4 -5 -6 7 -8 -9
max sum = 7

Hope this helps.

[cire]

As for the code, I'm not too impressed. A lot of times code gets into books that hasn't been either reviewed, or, shockingly, even compiled.

Whoever wrote this piece wasn't thinking very clearly. It tries to do a couple things the wrong way.

The code presented in the book is not C++, and was intended to show the divide and conquer approach to designing an algorithm. The "scanning" algorithm you used is presented later.

The code presented here is a bungled translation. Specifically when calculating the left portion of the crossing sum, one should begin at the midpoint and move left.

Line 19 should be: for (int i = mid; i >= lo; --i)

[dhayden]

The problem is more complex than Duoas's code handles. For example, in the sequence
-10, 11, 10, -3, 8, 3, 4, -6, 1
The maximum contiguous sequence is the one underlined (33). Duoas's code think's it's 21.

[n4nature]

The code presented here is a bungled translation. Specifically when calculating the left portion of the crossing sum, one should begin at the midpoint and move left.

Good observation cire. I doubt that fixing line 19 like you mention, would fix the problem. In this case, { -10, 11, 10, -10, 2, 3, -6, 1 } adding from mid to left would give temporary max of 11.

It looks like the algorithm doesn't work because left and right summations are done on n/2 elements in each call. So if max summation is formed by 2nd and 3rd element or say 6th and 7th together, then it fails to return the correct value.

[n4nature]

Just discount negative numbers, and find the largest sum of the remaining sequences.

How about ignoring negative numbers until I find the first positive and then keeping track of running max?

Kadane's algorithm

int RunningMax(int* arr, int size)
{
	int MaxSoFar = 0;
	int MaxEndingHere = 0;

	for (int i = 0; i < size; ++i)
	{
		MaxEndingHere = MaxEndingHere + arr[i];

		if (MaxEndingHere < 0)
		{
			MaxEndingHere = 0;
		}
		if (MaxEndingHere > MaxSoFar)
		{
			MaxSoFar = MaxEndingHere;
		}
	}

	return MaxSoFar;
}

[Duthomhas]

You're right.

/me stupid

[cire]

I doubt that fixing line 19 like you mention, would fix the problem.

It does, in fact, fix the problem.

It looks like the algorithm doesn't work because left and right summations are done on n/2 elements in each call. So if max summation is formed by 2nd and 3rd element or say 6th and 7th together, then it fails to return the correct value.

Re-read the algorithm description. The "cross sum" is all about "crossing" the right/left boundary.

[Edit: http://ideone.com/9T1MPi ]

[Duthomhas]

You cannot discount the possibility that all the numbers may be negative.

I don't know anything about that book. Improved me version:

int max_sum( int* arr, int n )
{
  if (!arr || !n) return 0;
  
  int max_sum = arr[0];
  vector <int> sums;
  int sum, i;
  
  i = 0;
  while (i < n)
  {
    // negative contiguous subsequences
    sum = 0;
    for (; (i < n) && (arr[i] < 0); ++i) 
    {
      if (arr[i] > max_sum) max_sum = arr[i];;
      sum += arr[i];
    }
    sums.push_back( sum );
    
    // positive contiguous subsequences
    if (i < n)
    {
      sum = 0;
      for (; (i < n) && (arr[i] >= 0); ++i) sum += arr[i];
      sums.push_back( sum );
    }
  }
  
  // Now for the O(n**2) stuff, but on the subsequence sums
  for (size_t i = 0; i < sums.size(); ++i)
  {
    sum = 0;
    for (size_t j = i; j < sums.size(); ++j)
    {
      sum += sums[j];
      if (sum > max_sum) max_sum = sum;
    }
  }
  
  return max_sum;
}

Now passes all the tests :OJ

Enter subsequence: -10, 11, 10, -3, 8, 3, 4, -6, 1
max sum = 33

Heh.

[cire]

You cannot discount the possibility that all the numbers may be negative.

Sure we can. That case is uninteresting and we can solve for it in O(n) time prior to running the more complex algorithm if necessary. ;-)

[n4nature]

cire, looked at your post on Ideone.com. I see you are using modern C++.

Would you recommend a good book on modern C++ usages? I loved the scott meyers series and I know there is another scott meyers book coming in November, which is for C++ 14.

If you guys have recommendations for good books on modern C++, I'd love to have them.

Thanks!

[LB]

http://stackoverflow.com/a/388282/1959975