题解 | #牛群的能量#

知识点

动态规划（线性）

思路分析

dp[i]表示第i位数前的最大能量区间和，如果其前一位dp[i-1]>=0，那么当前位置就可以衔接上上一段区间。若dp[i-1]<0，那么在当前位置重新开始 ，不选择之前的区间。同时，可以使用一个ans维护最大答案。 初始化：第0位必须拿，dp[0]=energy[0]

语言

c++

完整代码

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