想要精通算法和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;
}
如果是后者，我们有以下分析：[ 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]);
}
我们再加一个变量，用来存储数组总和即可，完整代码：
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.1 空间优化
先说下求最大值部分，参考：最大子数组和
int max = nums[0], pre = 0;
for (int num : nums) {
pre = Math.max(pre + num, num);
max = Math.max(max, pre);
}
也就是说，当我们发现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);
}
两个数组整合起来，再加一个变量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);
}
