Algorithm to return the maximum possible sum of subsequences in a sequence

Question

int maxSumRec(const vector<int> &a, int left, int right){

 if (left == right){

               if (a[left] > 0){
  return a[left];
               }
               else
                  return 0;

 }

 int center = (left + right)/2;
 int maxLeftSum = maxSumRec(a, left, center);
 int maxRightSum = maxSumRec(a, center+1, right);

 int leftBorderSum = 0; int leftBorderMax = 0; 
 for (int i = center; i >= left; i--){

  leftBorderSum += a[i];
  if (leftBorderSum > leftBorderMax){

   leftBorderMax = leftBorderSum;
  }
 }

 int rightBorderSum = 0; int rightBorderMax = 0;
 for (int i = center+1; i <= right; i++){

  rightBorderSum += a[i];
  if (rightBorderSum > rightBorderMax){

   rightBorderMax = rightBorderSum;
  }

 }

 int crossSum = rightBorderMax + leftBorderMax;

 return max3(maxLeftSum, maxRightSum, crossSum);

}

This is a O(NlogN) algorithm, I know it is not the best one. But just have several questions on it:

1. in the first if statement, why return 0 if a[left] < 0?

2. why need the 2 for loops? isn't the logic like this, find the max of the first half and the second half, and then add them to see if the addition is bigger than either. if it is this case, then we can directly jump to the last 2 lines?

Thanks very much,

Yue Harriet

Answer 1

OK, I figured out the 2nd question, because we have to take care of consecutive terms instead of jumping terms.

Answer 2

1. in the first if statement, why return 0 if a[left] < 0?

Because then the empty subsequence has the maximum sum, which is 0.

Answer 3

oh, i see i see.

thx, Svante :-) I didn't take into account that case. out of the box thinking, eh?