Maximum subarray by divide and conquer

Given an array containing positive and negative integers, we want to determine a subarray containing the largest sum of elements.

A couple of test cases, written in C++11 for GoogleTest, should make clearer the problem:

typedef std::array<int, 3> Info; // 1
typedef std::vector<int> Vector; // 2

TEST(MaxSub, Simple) // 3
{
  Vector input { 2, 3, 4, 5, 7 };

  unsigned last = input.size() - 1;
  Info sub = maxSubArray(input, 0, last);
  EXPECT_EQ(0, sub[0]);
  EXPECT_EQ(last, sub[1]);
  EXPECT_EQ(21, sub[2]);
}

TEST(MaxSub, Simple2) // 4
{
  Vector input {-2, -5, 6, -2, -3, 1, 5, -6};

  Info sub = maxSubArray(input, 0, input.size() - 1);
  EXPECT_EQ(2, sub[0]);
  EXPECT_EQ(6, sub[1]);
  EXPECT_EQ(7, sub[2]);
}

TEST(MaxSub, Negative) // 5
{
  Vector input {-2, -5, -2, -3, -6};

  Info sub = maxSubArray(input);
  EXPECT_EQ(0, sub[0]);
  EXPECT_EQ(0, sub[1]);
  EXPECT_EQ(0, sub[2]);
}

1. I want the function to return three values, the delimiting subarray indexes, and the found sum.
2. This is the container used to keep the input data.
3. Trivial case, all positive elements, the function would return 0, the last element index, and all element sum.
4. A typical case, nothing fancy.
5. If no positive element is in input, the result is an empty subarray.

We could use a divide and conquer approach to get a solution. Here is my C++11 implementation. Firstly, here is the divide part:

Info maxSubArray(const Vector& data, int left, int right)
{
  if(left == right) // 1
    return {{ left, right, data[left] }};

  int middle = (left + right) / 2; // 2

  Info subLeft = maxSubArray(data, left, middle); // 3
  Info subRight = maxSubArray(data, middle + 1, right);
  Info crossing = maxCrossing(data, left, middle, right); // 4

  return max(subLeft, subRight, crossing); // 5
}

1. If left and right index are actually the same, the problem is trivial.
2. Otherwise we split the interval in two parts. And
3. Recursively call the divide function on the left and right parts.
4. The hard job is done here. We need to check also the sequences that star before the middle point and end after it.
5. Once we get the three partial results, it is just a matter of checking which one has the highest sum and return it. To do that I have written a max() function that I guess you won't need to see to get how it works. In any case you will find it on github.

Let's see how to get the max subarray that crosses the central element. The idea is pretty simple, get the left and right max sum, starting from the middle point and moving outward, and then merge it:

Info maxCrossing(const Vector& data, int left, int middle, int right)
{
  int sum = 0;

  int maxLeft = middle;
  int leftSum = std::numeric_limits<int>::min();
  for(int i = middle; i >= left; --i) // 1
  {
    sum += data[i]; // 2
    if(sum > leftSum)
    {
      leftSum = sum;
      maxLeft = i;
    }
  }

  sum = 0; // 3
  int maxRight = middle + 1;
  int rightSum = std::numeric_limits<int>::min();
  for(int i = middle + 1; i <= right; ++i)
  {
    sum += data[i];
    if(sum > rightSum)
    {
      rightSum = sum;
      maxRight = i;
    }
  }

  return {{ maxLeft, maxRight, leftSum + rightSum }}; // 4
}

1. Loop on the elements, starting from the middle element to the leftmost one.
2. Tentatively add to the sum value the current value. If it is bigger to the precedently stored left sum value, adjust it and its leftmost index.
3. The right part is scanned specularly.
4. Put together left and right partial result to get the return value.

Full source C++11 code and a few test cases are on github.