LeetCode918-环形子数组的最大和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/maximum-sum-circular-subarray/

中文链接：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

提示：

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

题目详解

方法一：前缀和+单调队列。

  • 先将数组扩充一倍来模拟环状数组，然后求数组的前缀和。
  • 对以下标 i 结尾的子数组，其最优为 sum[i] - min(sum[j]), i - n <= j < i。
  • 为了快速知道当前组子数组的最小值，可以运用单调队列，保持队列从队头到队尾单调递增。
  • 遍历数组，队列长度超过限制则队首元素出队，进行结算，保持队列单调后当前元素入队。
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
28
public class LeetCode_00918 {

    public int maxSubarraySumCircular(int[] A) {
        int n = A.length;
        int[] sum = new int[2 * n + 1];
        for (int i = 1; i <= 2 * n; ++i) {
            if (i <= n) {
                sum[i] = sum[i - 1] + A[i - 1];
            } else {
                sum[i] = sum[i - 1] + A[i - n - 1];
            }
        }
        Deque<Integer> q = new ArrayDeque<>();
        q.offerLast(0);
        int res = A[0];
        for (int i = 1; i <= 2 * n; ++i) {
            if (!q.isEmpty() && i - q.peekFirst() > n) {
                q.pollFirst();
            }
            res = Math.max(res, sum[i] - sum[q.peekFirst()]);
            while (!q.isEmpty() && sum[i] <= sum[q.peekLast()]) {
                q.pollLast();
            }
            q.offerLast(i);
        }
        return res;
    }
}

方法二：动态规划。

  • 如果不存在环形则本题就是 LeetCode53-最大子序和。
  • 存在环形则说明最大子数组可能存在于首尾相连的子数组中，可以间接求得此值，通过元素总和减去最小子数组总和。
  • 结果就是这二者取最大值。
  • 存在一个特殊情况：所有元素不为正数，结果就是数组中最大的那个数，即 maxSum。
  • 因而，最终的结果为 maxSum > 0 ? Math.max(maxSum, tot - minSum) : maxSum。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00918 {

    public int maxSubarraySumCircular(int[] A) {
        int tot = 0;
        int curMax = 0;
        int maxSum = Integer.MIN_VALUE;
        int curMin = 0;
        int minSum = Integer.MAX_VALUE;
        for (int x : A) {
            tot += x;
            curMax = Math.max(curMax + x, x);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + x, x);
            minSum = Math.min(minSum, curMin);
        }
        return maxSum > 0 ? Math.max(maxSum, tot - minSum) : maxSum;
    }
}