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;
}