一、知识点:
动态规划
二、文字分析:
动态规划来解决。假设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; } }