连续子数组的最大值-C++-牛客BM72

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围: 1<=n<=2×10^5

−100<=a[i]<=100

要求:时间复杂度为 O(n)，空间复杂度为 O(n)

进阶:时间复杂度为 O(n)，空间复杂度为 O(1)

输入：[1,-2,3,10,-4,7,2,-5]

返回值：18

说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

设置一个当前连续序列的和cursum，表示当前一个连续子序列的和。从前向后遍历数组，将cursum加上当前位置的数据，如果cursum的值大于ans的值（ans记录出现过的最大连续序列的和），就用cursum的值更新ans的值，如果cursum的值小于0，则将cursum重新置0，并从下一个位置开始重新计算连续子序列的和（因为当前和为小于0，加上后面的只会变小，不会变大，所以重新开始计算）。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector array) {
        int ans = array[0], cursum = 0;
        int len = array.size();
        for(int i=0; i ans) ans = cursum;
            if(cursum <= 0) cursum = 0;
        }
        return ans;
    }
};