LeetCode 53. Maximum Subarray 最大连续字段和问题

考察：最大连续字段和问题。

解决问题时间复杂度：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;
}

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

考察：最大连续字段和问题。 解决问题时间复杂度：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; }