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

知识点

DP 前后缀分解

思路

合法的情况有第一种是正常的最大子段和，第二种是使用的左右两段的最大和，这可以预处理前缀的最大和和后缀的最大和，然后枚举前缀和对应最大的后缀，也可以处理。

当全是负数时会影响判断，可以先特判。

时间复杂度为

AC Code （C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param energy int整型vector 
     * @return int整型
     */
    int maxEnergyCircular(vector<int>& energy) {
        // 全为负数
        int mx = *max_element(energy.begin(), energy.end());
        if (mx < 0) return mx;

        int n = (int)energy.size();
        vector<int> l(n + 1), r(n + 1);
        for (int i = 1, sum = 0; i <= n; i ++) {
            sum += energy[i - 1];
            l[i] = max(l[i - 1], sum);
        }
        for (int i = 1, sum = 0; i <= n; i ++) {
            sum += energy[n - i];
            r[i] = max(r[i], sum);
        }
        int res = -2e9;
        for (int i = 0; i <= n; i ++) {
            res = max(res, l[i] + r[n - i]);
        }
        int sum = 0;
        for (auto x : energy) {
            sum += x;
            res = max(res, sum);
            if (sum < 0) sum = 0;
        }
        return res;
    }
};