考察:最大连续字段和问题。
解决问题时间复杂度:O(n)
问题隐含条件:如果给出的数集都是负数,那么最大连续字段和就是,最大的那个负数。
eg:{-2,-1} 结果应该输出 -1 而不是 0
int maxSubArray(int* nums, int numsSize) {
int maxSum = 0; //维护最大连续字段和
int currentMaxSum = 0;//当前最大和
int nextNum = 0;
int singleSum = nums[0]; //存在全是负数,则singleSum 代表最大的那个
int j = 0;
for (int i = 0; i < numsSize; i ++) {
nextNum = nums[i];
currentMaxSum += nextNum;
if (currentMaxSum > 0) {
maxSum = maxSum <= currentMaxSum ? currentMaxSum: maxSum;
} else {
currentMaxSum = 0;
j ++;
singleSum = singleSum < nextNum ? nextNum : singleSum;
}
}
maxSum = (j == numsSize) ? singleSum : maxSum;
return maxSum;
}