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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param energy int整型一维数组
 * @return int整型
 */
function maxEnergyCircular(energy) {
    // write code here
    let n = energy.length;
    let dp = [energy[0]]; // 用于存储每个位置的最大能量值，初始值为第一个位置的能量值

    let max = energy[0]; // 最大能量值的初始值设为第一个元素的能量值
    let sum = energy[0]; // 所有能量值的总和的初始值设为第一个元素的能量值

    // 正向遍历的过程中，寻找最大的能量值以及所有能量值的总和
    for (let i = 1; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], 0) + energy[i]; // 计算当前位置的最大能量值
        max = Math.max(max, dp[i]); // 更新最大能量值
        sum += energy[i]; // 累加所有能量值的总和
    }

    let min = energy[0]; // 初始值为第一个元素的能量值

    // 反向遍历的过程中，寻找所有连续子群的最小能量值
    for (let i = 1; i < n; i++) {
        dp[i] = Math.min(dp[i - 1], 0) + energy[i]; // 计算当前位置的最小能量值
        min = Math.min(min, dp[i]); // 更新最小能量值
    }

    // 不断更新所有连续子群的最大能量值，直到找到整个数组中最大的能量值
    return max < 0 ? max : Math.max(max, sum - min);
}
module.exports = {
    maxEnergyCircular: maxEnergyCircular,
};