LeetCode918 环形子数组最大值

思路：
1、破环成链。

由于是环形数组，则数组的末端会与开头相连呈环状。

只需要将长度为N的数组拷贝一次，拼接在原数组后，即得到长度为2N的数组，该数组即为环形数组。

如：原数组为123，则原数组为环形数组123123的子集。

2、前缀和。

要求环形数组中子数组的最大和，只需要求长度为2N的数组中长度不超过N的子数组的最大和。

构造前缀和后，求前缀和，即以右端点i与左端点j + 1所构成的子数组的最大和为Si - Sj 。
例：
[1,2,3,4]

构造前缀和：
[0,1,3,6,10]

子数组最大和：
10-0 = 10

3、单调队列（滑动窗口）。

滑动窗口的左端点为j，右端点为i，但需要维护j + 1到i，故窗口长度为i - j + 1 - 1 → i - j ≤ N。

由于求Si - Sj 最大，且Si是固定值，故Sj应该最小，即滑动窗口维护区间 S(j, i] 的最小值。

代码：

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length, m = n << 1;
        int[] sum = new int[m + 1];
        for (int i = 1; i <= m; ++i) {
            sum[i] = sum[i - 1] + nums[(i - 1) % n];
        }
        Deque<Integer> q = new LinkedList<>();    // 注意边界条件下标0
        q.add(0);
        int max = nums[0];
        for (int i = 1; i <= m; ++i) {
            if (!q.isEmpty() && q.peek() < i - n) {  // i-n 为窗口左边界，超过边界弹出一个元素。注意：这里deque里存的是下标
                q.poll();
            }
            max = Math.max(max, sum[i] - sum[q.peek()]);  
            while (!q.isEmpty() && sum[q.peekLast()] > sum[i]) { // TODO：待分析，这里注意循环的终止条件为sum[peekLas]<=sum[i]。也就是说，和比当前小的都不要，说明插入了负数。**
                q.pollLast();
            }
            q.add(i);
        }
        return max;
    }
}


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