【动态规划】力扣918. 环形子数组的最大和

给定一个长度为 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 。

动态规划

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        vector<int> leftMax(n);
        int pre = nums[0], res = nums[0], leftSum = nums[0] ;
        leftMax[0] = nums[0];
        for(int i = 1; i < n; i++){
            pre = max(nums[i], pre + nums[i]);
            res = max(res, pre);
            leftSum += nums[i];
            leftMax[i] = max(leftMax[i-1], leftSum);
        }

        int rightSum = 0;
        for(int i = n - 1; i > 0 ; i--){
            rightSum += nums[i];
            res = max(res, rightSum + leftMax[i-1]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度：O(n)，其中 n 是 nums 的长度。求解第一种情况的时间复杂度为 O(n)，求解 leftMax 数组和枚举后缀的时间复杂度为 O(n)，因此总的时间复杂度为 O(n)。

空间复杂度：O(n)，其中 n 是 nums 的长度。过程中我们使用 leftMax 来存放最大前缀和。

用动态规划的思路来讲，是要列出可能的情况。在这道题中一种情况是不跨越尾部，也就是正常的子段，另外一种是跨越尾部。针对特殊的跨越尾部的情况，使用leftMax来记录第 i 个元素之前的最大子段和，然后从右到左遍历数组，最后比较两种情况的最大值即可。

取反

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        int sum = nums[0];
        int preMax = nums[0], resMax = nums[0];
        int preMin = nums[0], resMin = nums[0];
        for(int i = 1; i < n; i++){
            preMax = max(nums[i], preMax + nums[i]);
            resMax = max(resMax, preMax);
            preMin = min(nums[i], preMin + nums[i]);
            resMin = min(resMin, preMin);
            sum += nums[i];
        }

        if(resMax < 0){
            return resMax;
        }
        else{
            return max(resMax, sum - resMin);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

这是一个更加巧妙的思路，并且有更低的空间复杂度。他的思想是所有数组元素之和减去中间的一段最小子段和，剩下的部分就是最大的经过头尾的子段和，再与正常子段和比较即可。要注意的是，当resMax < 0 的时候，sum - resMin返回的是一个空数组，这时候只要返回resMax。