题解 | #环形数组的连续子数组最大和#

(动态规划) $O(n)O(n)$

这道题目是 NC19 连续子数组的最大和 的升级版，增加了环形情况。

分两种情况考虑问题：

1. 无环情况下：求出连续子数组的最大值 res

2. 有环情况下：先求出无环情况下连续子数组的最小值 res2，然后用数组和 sum 减去最小值 res2 即为环形情况下的连续子数组最大值。

why? 因为数组的和是固定的，从中间挑一段和最小，那么剩下尾首相连的一段和就是最大的。这个说法应该是最容易理解的。

特殊情况：当 res < 0 时，观察状态转移公式：f[i] = max(f[i - 1], 0) + nums[i]，如果数组中有一个非负数，最大值也不会小于 0，那么说明全是负数，此时的最大值就是负数中最大的那个，直接返回即可。

时间复杂度

$O(n)O(n)$

空间复杂度

$O(1)O(1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (auto x : nums) sum += x;
        
        // 求无环情况下连续子数组的最大值
        int res = INT_MIN;
        for (int i = 0, last = 0; i < n; i ++ ) {
            last = max(last, 0) + nums[i];
            res = max(res, last);
        }
        
        // 求无环情况下连续子数组的最小值
        int res2 = INT_MAX;
        for (int i = 0, last = 0; i < n; i ++ ) {
            last = min(last, 0) + nums[i];
            res2 = min(res2, last);
        }
        
        // 如果无环情况下 res < 0 说明全是负数，那么此时的最大值就是负数中最大的那个，直接返回即可。
        // 有环情况下就没必要判断了。
        if (res < 0) return res;
        // sum - res2 表示环形情况下的连续子数组最大值，因为 res2 最小，sum - res2 就最大
        return max(res, sum - res2);
    }
};