void MaxSubSet_2(int nums[], int length)
{
if (length == 0)
return;
int start = 0;
int sum = nums[0];
int maxStart = 0;
int maxEnd = 0;
int maxSum = nums[0];
for (int i = 1; i < length; i++)
{
sum += nums[i];
if (sum > maxSum)
{
maxStart = start;
maxEnd = i;
maxSum = sum; //更新最大值
}
if (sum < 0) //放弃i之前的元素，他们的和开始变为为负数
{
start = i + 1; //下一个位置设置为开始位置
sum = 0;
}
}
cout << "Max: " << maxSum << " ( " << maxStart << ", " << maxEnd << " )" << endl;
}
当添加a[i],这一个元素的时候，判断如果加上a[i]之后的和大于当前的最大值；如果当前这段数据的和是开始变为负数的话，就要舍弃这段元素；更新开始的位置。
转载于:https://www.cnblogs.com/plxx/p/3232911.html
