Meximum Subarray Sum using Divide-And-Conquer

Question

Working on an implementation of finding the Greatest Contiguous Sum of a sequence using the Divide and Conquer method as seen here.

My return value is often incorrect. For example:

{5, 3} returns 5 instead of 8.
{-5, 3} returns 0 instead of 3.
{ 6, -5, 7 } returns 7 instead of 8. 

Other notes:

• decrementing or incrementing AT the first or last iterators throws an exception, saying that I either can't increment, decrement, or dereference at that point. There's a bug somewhere in GCSMid, I think, but I haven't been able to solve it.

• this implementation uses random-access iterators, signified as RAIter

  //function max- finds greatest number given 3 size_ts
  size_t max(size_t a, size_t b, size_t c)
  {
      if (a >= b && a >= c)
      {
          return a;
      }
  
      else if (b >= a && b >= c)
      {
          return b;
      }
      else
      {
          return c;
      }
  }
  
  
      //function gcsMid
      //main algorithm to find subsequence if it spans across the center line
      template<typename RAIter>
      size_t gcsMid(RAIter first, RAIter center, RAIter last)
      {
      size_t sum = 0;
      size_t leftSum = 0;
      size_t rightSum = 0;
  
      //to the left of center
      for (RAIter i = center; i > first; i--)
      {
          sum += *i;
          if(sum > leftSum)
          {
              leftSum = sum;
          } 
      }
  
      //to right of center
      sum = 0;
      for (RAIter j = (center + 1); j < last; j++)
      {
          sum += *j;
          if (sum > rightSum)
          {
              rightSum = sum;
          }
      }
  
      //return the sums from mid
      return leftSum + rightSum;
  }
  
  
  //main function to call
  template<typename RAIter>
  int gcs(RAIter first, RAIter last)
  {
      size_t size = distance(first, last);
  
      //base case is when the subarray only has 1 element. when first == last
      if (first == last || size == 1)
      {
          if (size < 1)
          {
              return 0;
          }
  
          if (*first < 0)
          {
              return 0;
          }
  
          return *first;
      }
  
      //middle point
      RAIter center = first + (size/2);
  
      //return max of leftsum, rightsum, and midsum
      return max(gcs(first, center),
                 gcs(center + 1, last),
                 gcsMid(first, center, last));    
  }
  

Answer 1

You have two problems with your code:

A. This loop:

for (RAIter i = center; i > first; i--)

does not include first in the loop. The reference algorithm does. You can't just use >= as the reference algorithm does as it doesn't work for iterators. Either add an extra bit of code to check first at the end, or change your loop so it somehow includes first (maybe a do while loop would suit better).

B. These definitions:

size_t sum = 0;
size_t leftSum = 0;
size_t rightSum = 0;

should not be size_t as size_t is unsigned. This means that when the sum goes negative, checks like if(sum > leftSum) no longer work, as the negative value (which underflows) is bigger than the positive value.

Change them to int.

The best way to find these kinds of errors is to run the code through a debugger. You can then step through each line of your code and see what the variable values are. This makes it easy to spot things like negative numbers becoming large positive numbers as above.