题解 | #牛群的最大能量环#

考察的知识点：动态规划；

解答方法分析：

1. 定义变量 ans1 用于存储最大能量值。
2. 创建一个大小为n的数组 dp1 ，用于存储最大能量值的动态规划数组。
3. 将 ans1 初始化为能量列表 energy 的第一个元素。
4. 使用循环遍历能量列表 energy ，从下标0开始。
5. 如果当前下标 i 为0，则将 dp1[i] 设置为 energy[i]。
6. 否则，判断上一个状态的最大能量值 dp1[i-1] 是否大于等于0，如果是，则将 dp1[i] 设置为 energy[i] 加上上一个状态的最大能量值，否则将 dp1[i] 设置为 energy[i]。
7. 更新 ans1 为 dp1[i] 和 ans1 之间的较大值。
8. 创建一个大小为n的数组 dp2 ，用于存储另一种情况下的动态规划数组。
9. 定义变量 ans2 用于存储另一种情况下的最小能量值。
10. 使用循环遍历能量列表 energy ，从下标1开始，到 n-1 结束。
11. 将 dp2[i] 设置为 energy[i] 和 dp2[i-1] 加上 energy[i] 之间的较小值。
12. 更新 ans2 为 dp2[i] ans2 之间的较小值。
13. 定义变量 sum 用于存储能量列表 energy 中所有元素的总和。
14. 使用循环遍历能量列表 energy ，将每个元素加到 sum 中。
15. 返回 ans1 和 sum - ans2 之间的较大值作为结果。

所用编程语言：C++；

完整编程代码：↓

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