子数组的最大累加和问题（贪心）

题意

给一个数字数组，求子数组和的最大值

思路分析

对于长度大于1的任意答案，考虑能否从这个答案眼花出更优的答案

如果答案选择数组两端有负数

那么把负数去掉，会得到更大的答案，所以两端一定都不是负数

如果答案两端外还有正数

那么包含这些正数，会得到更大的答案，所以答案的两端外一定都是非正数

如果答案一侧数组和为负数

去掉这一侧，会得到更大的答案

综上，答案选出的是一个 非正[非负 ... 非负] 非正 的子数组，且单侧部分数组和不为负

左侧为负

用变量cnt 记录从上一个选中的 非正[非负到目前位置的总和

如果数组左侧子数组为负，则cnt < 0直接抛弃掉，设置cnt = 0即可

最大值维护

如果每次计算出一个新的和cnt,而我们需要维护最大和，只需要外部增加变量每次取max()即可

for(...){
    ans = max(ans, cnt);
}

右侧为负

用变量cnt 记录从上一个选中的 非正[非负到目前位置的总和

如果数组右侧子数组为负，则上一个选中的位置到之前位置选出的数组能产生更大的和，现在的数组和更小，不会对最大和有影响。

题解

将上面的逻辑联系起来

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        int ans = arr[0]; // 初始化答案
        int cnt = 0; // 当前和
        for(auto v:arr){ // 枚举数组值
            cnt += v; // 更新当前和
            ans=max(ans, cnt); // 更新答案
            if(cnt < 0) cnt = 0; // 左侧为负
        }
        return ans;
    }
};

复杂度分析

空间复杂度 : 只用了常数个额外变量，所以空间复杂度为$O(1)O(1)$

时间复杂度 : 遍历时，每次计算是常数代价，所以总时间复杂度为$O(n)O(n)$