想要精通算法和SQL的成长之路 - 环形子数组的最大和

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 环形子数组的最大和

原题链接

在写这道题目之前，可以先看下这个题：最大子数组和 。本题是它的进阶版本，在原本的基础上，有一个环状的数组。那么我们如果将其平铺开来，就是一个两段数组拼接而成。

我们假设我们的数组是这样的：[ x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x] 。那么环形子数组的最大和，这个数组必定只有两种情况：

• 在数组内部：[ x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x]
• 由数组头和数组的尾部连结而成：[ x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x]

如果是前者，那么看 最大子数组和 的题解即可：

public int maxSubArray(int[] nums) {
    // 初始化dp数组
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int res = nums[0];
    // 遍历数组，dp[0]就是第一个数字它本身
    for (int i = 1; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        res = Math.max(res, dp[i]);
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

如果是后者，我们有以下分析：[ x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x]

• 左侧红色区域中：最右侧的数值必定是正数。 因为如果它是负数，那么它对于最大值的影响必定是负影响，不可能计入结果当中。同理，紧跟右侧的相邻数必定是负数。如果是正数，那么他也应该计入到结果中。
• 同理，右侧红色区域中：最左侧的数值必定是正数。 左侧相邻的数必定是负数。
• 即：[ x, x, x, 正数, 负数, x, x, x, x, x, x, x, x, 负数, 正数, x]

那么如果红色区域是：最大子数组和。中间部分就是：最小子数组和。

最大子数组和 = 数组总和 - 最小子数组和。这部分代码就是：

int min = dp[0];
// 这种情况我们视为左右两端成环的情况，那么求最小和数组的时候，必定不包含左右两侧端点
for (int i = 1; i < len - 1; i++) {
    dp[i] = nums[i] + Math.min(0, dp[i - 1]);
    min = Math.min(min, dp[i]);
}
1
2
3
4
5
6

我们再加一个变量，用来存储数组总和即可，完整代码：

public int maxSubarraySumCircular(int[] nums) {
    int len = nums.length;
    int[] dp = new int[len];
    dp[0] = nums[0];
    int res = dp[0];
    int sum = dp[0];
    for (int i = 1; i < len; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        res = Math.max(res, dp[i]);
        sum += nums[i];
    }

    int min = dp[0];
    for (int i = 1; i < len; i++) {
        dp[i] = nums[i] + Math.min(0, dp[i - 1]);
        min = Math.min(min, dp[i]);
    }
    return Math.max(sum - min, res);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.1 空间优化

先说下求最大值部分，参考：最大子数组和

int max = nums[0], pre = 0;
for (int num : nums) {
    pre = Math.max(pre + num, num);
    max = Math.max(max, pre);
}
1
2
3
4
5

也就是说，当我们发现dp整个运算过程中，只用到了两种变量：dp[i] 和dp[i-1]的时候，我们就可以用变量去替换整个数组。
那么求最小值部分同理：

int min = nums[0], pre2 = 0;
for (int num : nums) {
    pre2 = Math.min(pre2 + num, num);
    min = Math.min(min, pre2);
}
1
2
3
4
5

两个数组整合起来，再加一个变量sum代表数组总和，结果就出来了：

public int maxSubarraySumCircular(int[] nums) {
    int max = nums[0], pre = 0, min = nums[0], pre2 = 0, sum = 0;
    for (int num : nums) {
        // 求最大值和
        pre = Math.max(pre + num, num);
        max = Math.max(max, pre);
        // 求最小值和
        pre2 = Math.min(pre2 + num, num);
        min = Math.min(min, pre2);
        sum += num;
    }
    if (max < 0) {
        return max;
    }
    return Math.max(max, sum - min);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16