环形数组上的最大子数组和

摘要: 环形数组上的最大子数组和，有动态规划、前缀和两种解法。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在前一篇文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个问题有三种解法，都非常主流，并且各个方法都有它适用的变种问题。

本文我们看一个最直接的变种问题：环形数组上的最大子数组和。对于这种环形数组上的问题，一般我们可以想办法转化成普通数组上的问题，然后就可以套用普通数组上相同问题的解法了。

本文的两种做法对应了两种常见的将环形数组的问题转化为普通数组的问题的方法：

1. 将问题分为跨越数组分界点和不跨越数组分界点两种情况，分别解决。
2. 将原数组复制一份拼接到尾部，然后在拼成的数组上解决。

题目

918. 环形子数组的最大和

给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。

示例 1：
输入：[1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：[5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
示例 4：
输入：[3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
示例 5：
输入：[-2,-3,-1]
输出：-1
解释：从子数组 [-1] 得到最大和 -1

题解

算法1: 子数组是否跨越分界点分别讨论

在环形数组上的子数组，有两种情况，一种是子数组只有一个区间 [i, j]，其中 0 <= i <= j <= n-1；另一种是子数组是由头和尾两个区间组成的，也就是 [0, j] 和 [i, n-1]，其中 0 <= j < i <= n-1。

也就是说当数组可以循环时，子数组可能是单区间或双区间。

对于单区间的情况，我们还是可以按照常规的最大子数组和的算法，得到单区间情况下的数组 A 的最大子数组和。

对于双区间[0, j], [i, n - 1] 的情况，两个区间表示的子数组和取得最大值时，子数组 [j + 1, i - 1] 的和取到最小值。

因此还是可以用常规的最大子数组和的算法求数组 A 上的最小子数组和，sum(A) 与该最小子数组和的差就是双区间情况下的最大子数组和。

代码(C++)

常规情况下的最大/最小子数组和，用之前的文章 最大子数组和的三种解法 提到的三种方法均可以，这里使用的是动态规划。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        if(n == 1) return A[0];

        // 单区间最大子数组和
        int sum = A[0], sum1 = A[0], ans1 = A[0];
        for(int i = 1; i < n; ++i)
        {
            sum += A[i];
            sum1 = A[i] + max(sum1, 0);
            ans1 = max(ans1, sum1);
        }
        if(n == 2) return ans1;

        // 双区间的最大字数组和
        int sum2 = A[1], ans2 = A[1];
        for(int i = 1; i < n - 1; ++i)
        {
            sum2 = A[i] + min(sum2, 0);
            ans2 = min(ans2, sum2);
        }
        ans2 = sum - ans2;
        return max(ans1, ans2);
    }
};

算法2: 将原数组复制一份拼到后面

本题与常规的最大子数组和问题的唯一区别是数组是环形的，环形数组的子数组可能是单区间的 [i, j]，也可能是双区间的 [0, j], [i, n - 1]。

那么很自然地想到一种比较省事的办法，就是把原数组复制一份接到后面形成新数组：

A.insert(A.end(), A.begin(), A.end());

这样的话就不用考虑子数组是单区间的还是双区间的了，对于拼接成的数组来说都是单区间的。

于是在新数组上就可以用常规的最大子数组和的算法做了，只是需要额外考虑一个新数组的子数组的长度不能大于原数组长度即可。

代码(C++)

常规情况下的最大/最小子数组和，用之前的文章 最大子数组和的三种解法 提到的三种方法均可以，这里使用的是前缀和 + 单调队列。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        if(n == 1) return A[0];
        A.insert(A.end(), A.begin(), A.end());
        deque<int> deq;
        vector<int> sums(n * 2 + 1, 0);
        for(int i = 0; i < n * 2; ++i)
            sums[i + 1] = A[i] + sums[i];
        int ans = INT_MIN;
        deq.push_back(0);
        for(int j = 1; j <= n * 2; ++j)
        {
            int pj = sums[j];
            int pi = sums[deq.front()];
            ans = max(ans, pj - pi);
            while(!deq.empty() && sums[deq.back()] >= pj)
                deq.pop_back();
            deq.push_back(j);
            if(j - deq.front() == n)
                deq.pop_front();
        }
        return ans;
    }
};

---