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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param energy int整型一维数组 
     * @return int整型
     */
    public int maxEnergyCircular (int[] energy) {
        // write code here
        // 情况1:最大能量值不跨数组，直接请求最大能量值
        // 情况2:最大能量值跨数组，求出最小能力值，总和减去最小能力值 即为 最大能量值
        // 取情况1和情况2的最大能量值
        // 注意情况2中可能为0，即一个不取，这时应该取max

        int[] dp1 = new int[energy.length];
        int max = energy[0];
        dp1[0] = energy[0];
        for (int i = 1; i < energy.length; i++) {
            dp1[i] = Math.max(energy[i],dp1[i-1]+energy[i]);
            max = Math.max(max, dp1[i]);
        } 

        int[] dp2 = new int[energy.length];
        int min = energy[0];
        dp2[0] = energy[0];
        int sum = energy[0];
        for (int i = 1; i < energy.length; i++) {
            dp2[i] = Math.min(energy[i],dp2[i-1]+energy[i]);
            min = Math.min(min, dp2[i]);
            sum += energy[i];
        } 

        return sum - min == 0 ? max : Math.max(max, sum - min);
    }
}