Algorithm for returning 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 O (NlogN) algorithm, I know that it is not the best. But there are a few questions to this:

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

• Why are loops 2 needed? this is not a logic like this, find the maximum of the first half and second half, and then add them to see if the addition is larger. if so, then can we go straight to the last 2 lines?

Many thanks,

Yue Harriet

Answer 1

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

Since then the empty subsequence has a maximum sum of 0.

Answer 2

, , .