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

知识点：

动态规划

分析:

会了牛群的能量，也就会这个了。 变换就是变为了环形数组

分两种情况。

(1)答案在数组中间，就是最大子序和。例如[1,-2,3,-2]；

(2)答案在数组两边，例如[5,-3,5]最大的子序和就等于数组的总和SUM - 最小的子序和。

(一种特殊情况是数组全为负数，也就是SUM-最小子序和==0，最大子序和等于数组中最大的那个)。

编程语言：

C++

完整代码：

int maxEnergyCircular(vector<int>& energy) {
        int total = 0, curMax = 0, maxSum = energy[0], curMin = 0, minSum = energy[0];
        for (int a : energy) {
            total += a;
            curMax = max(curMax + a, a);
            maxSum = max(maxSum, curMax);
            curMin = min(curMin + a, a);
            minSum = min(curMin, minSum);
        }

        if (maxSum >= 0) {
            return max(total - minSum, maxSum);
        } else {
            return maxSum;
        }
    }