题解 | #牛群的能量#

牛群的能量

https://www.nowcoder.com/practice/00f87ddcd18842d0824d487fd70a730e

一、知识点:

动态规划

二、文字分析:

动态规划来解决。假设dp[i]表示以第i个元素结尾的子群的最大能量值之和。对于当前的dp[i],考虑两种情况:包含第i个元素和不包含第i个元素。

如果包含第i个元素,那么最大能量值之和就是dp[i-1]+energy[i],即以第i-1个元素结尾的子群的最大能量值之和加上第i个元素的能量值。

如果不包含第i个元素,那么最大能量值之和就是energy[i],即以第i个元素为起点的子群的最大能量值之和。

所以,可以得到递推公式:dp[i] = max(dp[i-1]+energy[i], energy[i])。

时间复杂度为O(n),空间复杂度为O(n)。

三、编程语言:

java

四、正确代码:

import java.util.*;


public class Solution {
    public int maxEnergy(int[] energy) {
        int n = energy.length;
        int[] dp = new int[n];
        dp[0] = energy[0];
        int maxEnergy = dp[0];
        
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i-1] + energy[i], energy[i]);
            maxEnergy = Math.max(maxEnergy, dp[i]);
        }
        
        return maxEnergy;
    }
}

全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务