advancing10

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/maximum-sum-circular-subarray/]

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

在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，而当 i >= 0 时 C[i+A.length] = C[i]）

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

示例 1：

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

示例 2：

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

示例 3：

1
2
3
输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4

示例 4：

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

示例 5：

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

提示：

  1. -30000 <= A[i] <= 30000
  2. 1 <= A.length <= 30000

算法描述

首先，我们可以在一个定长数组上完成这个问题。

我们可以认为循环数组 A 的任意子段，一定是定长数组 A+A 的任一个子段。

例如，对于循环数组 A = [0,1,2,3,4,5]，那么它的子段 [4,5,0,1] 一定也是定长数组 [0,1,2,3,4,5,0,1,2,3,4,5] 的子段。令 B = A + A 就是这个定长数组。

假定 N = A\text{.length}N=A.length，考虑前缀和

P_k = B[0] + B[1] + \cdots + B[k-1]P**k=B[0]+B[1]+⋯+B[k−1]

然后，考虑最大的 P_j - P_iPj−Pi 其中 j - i \leq Nj−i≤N。

考虑第 jj 个候选答案：对于固定 jj 的最优结果 P_j - P_iPj−Pi。我们希望一个 ii 使得 P_iP**i 尽量小 并且满足 j - N \leq i < jj−N≤i<j，称对于第 jj 个候选答案的的最优 ii。我们可以用优先队列实现它。

算法

迭代 jj，每次计算第 jj 个候选答案。我们维护一个 queue 保存可能的最优 ii。

核心想法是如果 i_1 < i_2i1<i2 且 P_{i_1} \geq P_{i_2}P*i1≥P*i2，那么就不再需要考虑 i_1i1。

查看代码了解更多实现细节。

  • Java
  • Python

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
         int n = A.size();
        for(int i=0;i<n;i++)A.push_back(A[i]);
        vector<int> S(n*2+1,0);
        for(int i=0;i<n*2;i++)S[i+1] = S[i]+A[i];
        deque<int> q;
        
        int res = INT_MIN;
        
        q.push_back(0);
        for(int i=1;i<=n*2;i++){
            if(q.size()&&i-n>q.front())q.pop_front();
            res = max(res,S[i] - S[q.front()]);
            while(q.size()&&S[q.back()]>=S[i])q.pop_back();
            q.push_back(i);
        }
        
        return res;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int N = A.length;

        int[] P = new int[2*N+1];
        for (int i = 0; i < 2*N; ++i)
            P[i+1] = P[i] + A[i % N];

        int ans = A[0];
        Deque<Integer> deque = new ArrayDeque();
        deque.offer(0);

        for (int j = 1; j <= 2*N; ++j) {
            if (deque.peekFirst() < j-N)
                deque.pollFirst();

            ans = Math.max(ans, P[j] - P[deque.peekFirst()]);

            while (!deque.isEmpty() && P[j] <= P[deque.peekLast()])
                deque.pollLast();

            deque.offerLast(j);
        }

        return ans;
    }
}