子数组的最大累加和问题(贪心)

题意

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

思路分析

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

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

alt

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

如果答案两端外还有正数

alt

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

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

alt

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


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

左侧为负

用变量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)