最大子数组和[中等]

一、题目

给定一个长度为n的环形整数数组nums，返回nums的非空子数组的最大可能和。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上，nums[i]的下一个元素是nums[(i + 1) % n]，nums[i]的前一个元素是nums[(i - 1 + n) % n]。

子数组 最多只能包含固定缓冲区nums中的每个元素一次。形式上，对于子数组nums[i], nums[i + 1], ..., nums[j]，不存在i <= k1, k2 <= j其中k1 % n == k2 % n。

示例 1：
输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组[3]得到最大和3

示例 2：
输入：nums = [5,-3,5]
输出：10
解释：从子数组[5,5]得到最大和5 + 5 = 10

示例 3：
输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组[3]和[3,-2,2]都可以得到最大和3

n == nums.length
1 <= n <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104

二、代码

【1】动态规划： 求解普通数组的最大子数组和是求解环形数组的最大子数组和问题的子集。设数组长度为n，下标从0开始，在环形情况中，答案可能包括以下两种情况：
1、构成最大子数组和的子数组为nums[i:j]，包括nums[i]到nums[j−1]共j−i个元素，其中0≤i<j≤n
2、构成最大子数组和的子数组为nums[0:i]和nums[j:n]，其中0<i<j<n。

第二种情况中，答案可以分为两部分，nums[0:i]为数组的某一前缀，nums[j:n]为数组的某一后缀。求解时，我们可以枚举j，固定sum(nums[j:n])的值，然后找到右端点坐标范围在[0,j−1]的最大前缀和，将它们相加更新答案。

右端点坐标范围在[0,i]的最大前缀和可以用leftMax[i]表示，递推方程为：leftMax[i]=max⁡(leftMax[i−1],sum(nums[0:i+1])

至此，我们可以使用以上方法求解出环形数组的最大子数组和。特别需要注意的是，本题要求子数组不能为空，我们需要在代码中做出相应的调整。

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        // 对坐标为 0 处的元素单独处理，避免考虑子数组为空的情况
        leftMax[0] = nums[0];
        int leftSum = nums[0];
        int pre = nums[0];
        int res = nums[0];
        for (int i = 1; i < n; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            res = Math.max(res, pre);
            leftSum += nums[i];
            leftMax[i] = Math.max(leftMax[i - 1], leftSum);
        }

        // 从右到左枚举后缀，固定后缀，选择最大前缀
        int rightSum = 0;
        for (int i = n - 1; i > 0; i--) {
            rightSum += nums[i];
            res = Math.max(res, rightSum + leftMax[i - 1]);
        }
        return res;
    }
}

时间复杂度： O(n)，其中n是nums的长度。求解第一种情况的时间复杂度为O(n)，求解leftMax数组和枚举后缀的时间复杂度为O(n)，因此总的时间复杂度为O(n)。
空间复杂度： O(n)，其中n是nums的长度。过程中我们使用leftMax来存放最大前缀和。

【2】取反： 对于第二种情况，即环形数组的最大子数组和为nums[0:i]和nums[j:n]，我们可以找到普通数组最小的子数组nums[i:j]即可。而求解普通数组最小子数组和的方法与求解最大子数组和的方法完全相同。

令maxRes是普通数组的最大子数组和，minRes是普通数组的最小子数组和，我们可以将maxRes与∑i=0nnums[i]−minRes取最大作为答案。

需要注意的是，如果maxRes<0，数组中不包含大于等于0的元素，minRes将包括数组中的所有元素，导致我们实际取到的子数组为空。在这种情况下，我们只能取maxRes作为答案。

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int preMax = nums[0], maxRes = nums[0];
        int preMin = nums[0], minRes = nums[0];
        int sum = nums[0];
        for (int i = 1; i < n; i++) {
            preMax = Math.max(preMax + nums[i], nums[i]);
            maxRes = Math.max(maxRes, preMax);
            preMin = Math.min(preMin + nums[i], nums[i]);
            minRes = Math.min(minRes, preMin);
            sum += nums[i];
        }
        if (maxRes < 0) {
            return maxRes;
        } else {
            return Math.max(maxRes, sum - minRes);
        }
    }
}

时间复杂度： O(n)，其中n是nums的长度。
空间复杂度： O(1)。过程中只是用到了常数个变量。

【3】单调队列： 我们可以将数组延长一倍，即对于i≥n的元素，令nums[i]=nums[i−n]。

然后，对于第二种情况，nums[0:i]和nums[j:n]可以组成成连续的一段：

因此，问题转换为了在一个长度为2n的数组上，寻找长度不超过n的最大子数组和。

我们令si=∑i=0inums[i]为前缀和，如果不规定子数组的长度，只需找到最大的si−sj，其中j<i。

现在，我们只能考虑所有满足i−n≤j<i的j，用单调队列维护该集合。具体的：
1、遍历到i时，单调队列头部元素下标若小于i−n，则出队。该过程一直进行，直至队列为空或者队头下标大于等于i−n。
2、取队头元素作为j，计算si−sj，并更新答案。
3、若队列尾部元素k满足sk≥si，则出队，该过程一直进行，直至队列为空或者条件不被满足。因为k<i，k更容易被步骤1剔出，并且作为被减项，sk比si更大，更不具有优势。综上si要全面优于sk。

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        Deque<int[]> queue = new ArrayDeque<int[]>();
        int pre = nums[0], res = nums[0];
        queue.offerLast(new int[]{0, pre});
        for (int i = 1; i < 2 * n; i++) {
            while (!queue.isEmpty() && queue.peekFirst()[0] < i - n) {
                queue.pollFirst();
            }
            pre += nums[i % n];
            res = Math.max(res, pre - queue.peekFirst()[1]);
            while (!queue.isEmpty() && queue.peekLast()[1] >= pre) {
                queue.pollLast();
            }
            queue.offerLast(new int[]{i, pre});
        }
        return res;
    }
}