题解 | #牛群的能量#

1. 题目考察的知识点

动态规划

2. 题目解答方法的文字分析

用 f(i)代表以第 i个数结尾的「和最大子群能量值之和」，设数组的长度为n,则本题的答案时从0到n-1这n个f(i)的最大值。因此我们只需要求出每个位置的 f(i)，然后返回 f数组中的最大值即可。

那么我们如何求 f(i) 呢？我们可以考虑 energy[i]单独成为一段还是加入 f(i−1)对应的那一段，则该题的转移方程为： f(i) = max(f(i-1),f(i-1）+ energy[i]); 考虑到 f(i)只和 f(i−1)相关，于是我们可以只用一个变量 pre来维护对于当前 f(i) 的 f(i−1)的值是多少。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param energy int整型一维数组 
     * @return int整型
     */
    public int maxEnergy (int[] energy) {
        int pre=0,ans=energy[0];
        for(int i=0;i<energy.length;i++){
            pre=Math.max(pre+energy[i],energy[i]);
            ans=Math.max(pre,ans);
        }
        return ans;
    }
}