最大子数组和（最大子段和）(二)
right)
{
int maxsum = INT_MIN, sum = 0;
int begin = 0;
for(int i = 0; i < vec.size(); i++)
{
if(sum >= 0)
{
sum += vec[i];
}
else
{
sum = vec[i];
begin = i;
}
if(maxsum < sum)
{
maxsum = sum;
left = begin;
right = i;
}
}
return maxsum;
}
如果数组是循环的，该如何呢
这时分两种情形（图中红色方框表示求得的最大子数组，left、right分别是子数组的开始和结尾）：
（1）如下图最大的子数组没有跨过vec[n-1]到vec[0], 这就是每循环的情况
image
（2）如下图，最大的子数组跨过vec[n-1]到vec[0]
image
对于第二种情形，相当于从原数组中挖掉了一块(vec[right+1], …, vec[left-1]) ,那么我们只要使挖掉的和最小即可，求最小子数组和最大子数组类似，代码如下，以下代码在九度oj1572首尾相连数组的最大子数组和通过测试（测试需要，以下代码当数组全是负数时，输出0）：
int maxSumCycle(vector&vec, int &left, int&right)
{
int maxsum = INT_MIN, curMaxSum = 0;
int minsum = INT_MAX, curMinSum = 0;
int sum = 0;
int begin_max = 0, begin_min = 0;
int minLeft, minRight;
for(int i = 0; i < vec.size(); i++)
{
sum += vec[i];
if(curMaxSum >= 0)
{
curMaxSum += vec[i];
}
else
{
curMaxSum = vec[i];
begin_max = i;
}
if(maxsum < curMaxSum)
{
maxsum = curMaxSum;
left = begin_max;
right = i;
}
///////////////求和最小的子数组
if(curMinSum <= 0)
{
curMinSum += vec[i];
}
else
{
curMinSum = vec[i];
begin_min = i;
}
if(minsum > curMinSum)
{
minsum = curMinSum;
minLeft = begin_min;
minRight = i;
}
}
if(maxsum >= sum - minsum)
return maxsum;
else
{
left = minRight+1;
right = minLeft-1;
return sum - minsum;
}
}