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

前言

想要精通算法和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);
}