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);
}
这是一个复杂度为 O(NlogN) 的算法,我知道它不是最好的。但是有几个问题:
在第一个 if 语句中,如果 a[left] < 0,为什么返回 0?
为什么需要 2 个 for 循环?不是这样的逻辑吗,求前半部分和后半部分的最大值,然后相加,看相加是否比两者都大。 如果是这种情况,那我们可以直接跳到最后2行吗?
非常感谢,
岳哈丽特
最佳答案
- in the first if statement, why return 0 if a[left] < 0?
因为此时空子序列的和最大,为0。
关于c++ - 返回序列中子序列的最大可能总和的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/624540/