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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

动态规划

题目解答方法的文字分析

这道题是之前的题目的一个扩展，这次数组是一个环形整数数组，即末端与开头相连呈环状。我们需要求解一个连续子群的最大能量值之和。

对于这种环形数组的情况，我们可以分为两种情况进行考虑：

1. 没有跨过环形边界，即不需要考虑环形问题，这种情况下，我们可以直接使用之前的方法求解最大子数组和。
2. 子数组跨过了环形边界，这时我们需要通过数组和减去未选取部分的子数组和，得到跨边界的子数组和。然后再求得不考虑环形的情况下，可以得到的最小子数组和，以确保数组和减去该子数组和能够得到最大的子数组和。

还有一个需要注意的点，在于如果整个数组的元素都是负数，则最大子数组和为负数，最小子数组和为整个数组和，此时直接返回最大子数组和即可。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    int maxEnergyCircular(vector<int>& energy) {
        int n = energy.size();
        if (n == 0) {
            return 0;
        }

        // 求解不考虑环形边界的最大子数组和
        int maxSum = energy[0];
        int currentMax = energy[0];
        for (int i = 1; i < n; ++i) {
            currentMax = max(energy[i], currentMax + energy[i]);
            maxSum = max(maxSum, currentMax);
        }

        // 求解数组的和
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += energy[i];
        }

        // 求解跨边界的子数组和
        int minSum = energy[0];
        int currentMin = energy[0];
        for (int i = 1; i < n - 1; ++i) {
            currentMin = min(energy[i], currentMin + energy[i]);
            minSum = min(minSum, currentMin);
        }

        // 求得能量值最大的子数组和
        int maxEnergyValue = max(maxSum, sum - minSum);

        // 如果整个数组的元素都是负数，则maxSum为负数，直接返回maxSum
        if (maxEnergyValue <= 0) {
            return maxSum;
        }

        return maxEnergyValue;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！