题解 | #牛群的能量# 最大的连续子段和

知识点

动态规划

思路

我们可以维护一个当前的前缀和，然后用当前的前缀和去更新答案。当当前的前缀和小于0的时候我们可以认为它对答案没有贡献，置为0。

时间复杂度为

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param energy int整型vector 
     * @return int整型
     */
    const int INF = 1e9;
    int maxEnergy(vector<int>& energy) {
        int n = energy.size();
        int cur = 0, res = -INF;
        for (auto x : energy) {
            cur += x;
            res = max(res, cur);
            if (cur < 0) cur = 0;
        }
        return res;
    }
};