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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param energy int整型一维数组
     * @return int整型
     */
    public int maxEnergyCircular (int[] energy) {
        // write code here
         int total = 0, curMax = 0, maxSum = energy[0], curMin = 0, minSum = energy[0];
        for (int a : energy) {
            total += a;
            curMax = Math.max(curMax + a, a);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + a, a);
            minSum = Math.min(curMin, minSum);
        }
 
        if (maxSum >= 0) {
            return Math.max(total - minSum, maxSum);
        } else {
            return maxSum;
        }
    }
}

知识点：

1. 动态规划：一种通过将问题分解成子问题，并存储子问题的解来解决问题的方法。

2. 环形数组问题：在数组首尾相连的情况下，求解子数组的最大和问题。

解题思路：

1. 变量total，用于记录数组energy中所有元素的总和。
2. curMax、maxSum，分别表示当前连续子数组的最大和和全局最大和，初始值都为energy[0]。
3. curMin、minSum，分别表示当前连续子数组的最小和和全局最小和，初始值都为energy[0]。
4. 循环遍历数组energy：将当前元素累加到total中。更新curMax的值，取当前元素与curMax加上当前元素的较大值。更新maxSum的值，取maxSum与curMax的较大值。更新curMin的值，取当前元素与curMin加上当前元素的较小值。更新minSum的值，取minSum与curMin的较小值。
5. 如果maxSum大于等于0，则返回total减去minSum和maxSum的较大值；否则，返回maxSum。