最大公共子序列Code

int maxSumRec(const vector<int>& a, int left, int right)
{
if (left == right)
{
if (a[left] > 0)
{
return a[left];
}
else
{
return 0;
}
}</int>

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

int leftBorderSum = 0, maxLeftBorderSum = 0;
for (int i = center; i >= left; --i)
{
    leftBorderSum += a[i];
    if (leftBorderSum > maxLeftBorderSum)
    {
        maxLeftBorderSum = leftBorderSum;
    }
}

int rightBorderSum = 0, maxRightBorderSum = 0;
for (int i = center + 1; i <= right; ++i)
{
    rightBorderSum += a[i];
    if (rightBorderSum > maxRightBorderSum)
    {
        maxRightBorderSum = rightBorderSum;
    }
}

return max3<int>(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);

}

int maxSum4(const vector<int>& a,int& leftposition,int& rightposition)
{
int thisSum = 0, maxSum = 0;
leftposition = rightposition = 0;
for (int i = 0; i < a.size(); ++i)
{
thisSum += a[i];
if (thisSum > maxSum)
{
maxSum = thisSum;
rightposition = i;
}
else if (thisSum < 0)
{
thisSum = 0;
leftposition = i + 1;
}
}</int>

return maxSum;

}