918. 环形子数组的最大和(中等)

Posted on Edited on In Views:

1，问题描述

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 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • n == nums.length
  • 1 <= n <= 3 * 10^4
  • -3 * 104 <= nums[i] <= 3 * 10^4

2，初步思考

​ 相似的题目是53，只是多了一个环
​ 有好几种解法

3，代码处理

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class _918环形子数组的最大和 {

    // 逆向思维
    // 有两种可能：1️⃣，首位不同时在子数组中；2️⃣，首位相同在子数组中
    // 转换为：1️⃣，nums内部，2️⃣，nums外部=sum-min最小子数组
    // 时间复杂度：O(n)，空间复杂度：O(1)
    public int maxSubarraySumCircular_option(int[] nums) {
        int len = nums.length;
        int sum = nums[0];
        int preMax = nums[0];
        int resMax = nums[0];
        int preMin = nums[0];
        int resMin = nums[0];
        for (int i = 1; i < len; i++) {
            sum += nums[i];
            preMax = Math.max(nums[i], nums[i] + preMax);
            resMax = Math.max(resMax, preMax);
            preMin = Math.min(nums[i], nums[i] + preMin);
            resMin = Math.min(resMin, preMin);
        }// 必须要选择一个数据
        return Math.max(resMax, sum - resMin == 0 ? resMax : (sum - resMin));
    }

    // 官方题解
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        leftMax[0] = nums[0];
        int leftSum = nums[0];
        int pre = nums[0];
        int res = nums[0];
        for (int i = 1; i < n; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            res = Math.max(res, pre);
            leftSum += nums[i];// 前缀和
            leftMax[i] = Math.max(leftMax[i - 1], leftSum);// 最大前缀和
        }// 从左往右

        int rightSum = 0;
        for (int i = n - 1; i > 0; i--) {
            rightSum += nums[i];
            res = Math.max(res, rightSum + leftMax[i - 1]);
        }// 从右往左
        return res;
    }

    // 解法：前缀和
    public int maxSubarraySumCircular_prefix_sum(int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n * 2];
        prefixSum[0] = nums[0];
        int sum = nums[0];
        int min = nums[0];
        int max = nums[0];
        int res = nums[0];
        for (int i = 1; i < n; i++) {
            sum += nums[i];
            if (sum > max) {
                max = sum;
                res = Math.max(res, max - min);
            } else if (sum < min) {
                min = sum;
            }
            prefixSum[i] = sum;
        }
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            if (sum > max) {
                max = sum;
                res = Math.max(res, max - min);
            } else if (sum < min) {
                min = sum;
            }
            prefixSum[i + n] = sum;
        }
        return res;
    }

    public int maxSubarraySumCircular_monostone_stack(int[] nums) {
        int n = nums.length;
        Deque<int[]> queue = new ArrayDeque<int[]>();
        int pre = nums[0], res = nums[0];
        queue.offerLast(new int[]{0, pre});
        for (int i = 1; i < 2 * n; i++) {
            while (!queue.isEmpty() && queue.peekFirst()[0] < i - n) {
                queue.pollFirst();
            }// 1，遍历到 i 时，单调队列头部元素下标若小于 i−n，则出队。该过程一直进行，直至队列为空或者队头下标大于等于 i−n。
            pre += nums[i % n];// 累加前缀和
            res = Math.max(res, pre - queue.peekFirst()[1]);// 2，取队头元素作为 j，计算 si−sj，更新答案。
            while (!queue.isEmpty() && queue.peekLast()[1] >= pre) {
                queue.pollLast();
            }// 3，若队列尾部元素 k 满足 sk≥si，则出队，该过程一直进行，直至队列为空或者条件不被满足。因为 k<i，k 更容易被步骤 1 剔出，并且作为被减项，sk比si 更大，更不具有优势。综上 si 要全面优于sk
            queue.offerLast(new int[]{i, pre});
        }
        return res;
    }


    public static void main(String[] args) {
        _918环形子数组的最大和 maxSubarraySumCircular = new _918环形子数组的最大和();
//        System.out.println(maxSubarraySumCircular.maxSubarraySumCircular_option(new int[]{1, -2, 3, -2}));
        System.out.println(maxSubarraySumCircular.maxSubarraySumCircular_prefix_sum(new int[]{5, -3, 5}));
//        System.out.println(maxSubarraySumCircular.maxSubarraySumCircular_prefix_sum(new int[]{-3, -2, -3}));
//        System.out.println(maxSubarraySumCircular.maxSubarraySumCircular_prefix_sum(new int[]{3, -2, 2, -3}));
    }

}