最大子数组和「变题」

开头先来一个小插曲，关于「子数组」相关的总结可见 秒杀子数组类题目 子数组之滑动窗口篇

这个题目是一个入门的 DP，先直接给出代码：


public int maxSubArray(int[] nums) {
    int dp = 0, ans = nums[0];
    for (int i = 0; i < nums.length; i++) {
        if (dp < 0) dp = nums[i];
        else dp += nums[i];
        ans = Math.max(ans, dp);
    }
    return ans;
}

这么简单，还总结干嘛！！因为看到很多人说这个题目考了很多「变题」

变题一：输出「最大和的连续子数组」

用三个变量temp, left, right记录每次更新时的下标

temp记录每次dp < 0时重新求和的下标，这可能是下一次更新最大值的起点
left记录更新最大值时的起点，即temp
right记录更新最大值时的终点


xxxxxxxxxx
public int maxSubArray(int[] nums) {
    int dp = 0, ans = nums[0];
    int temp = 0, left = 0, right = 0;
    for (int i = 0; i < nums.length; i++) {
        if (dp < 0) {
            temp = i;    // 更新 temp
            dp = nums[i];
        } else dp += nums[i];
        if (ans < dp) {
            left = temp; // 更新 left
            right = i;   // 更新 right
            ans = dp;
        }
    }
    // 输出
    List<Integer> path = new ArrayList<>();
    for (int i = left; i <= right; i++) {
        path.add(nums[i]);
    }
    System.out.println(path.toString());
    // end
    return ans;
}

变题二：如下所示

可见题目长度最小的子数组


xxxxxxxxxx
给一个数组，以及一个数：如 [1, 3, 4, 3, 9, 1]， k = 12, 返回其中最短的大于等于 k 的子数组。若无满足条件则返回 0
Input: 
[1, 3, 4, 3, 9, 1]
12
Output:
2 // 因为最短的是 [3, 9] 长度 2

本题可以直接暴力，也可以使用「滑动窗口」，之前有过相关总结 秒杀子数组类题目

具体代码如下：


xxxxxxxxxx
public int minSubArrayLen(int target, int[] nums) {
    int sum = 0, l = 0, r = 0, ans = (int) 1e5 + 10;
    while (r < nums.length) {
        sum += nums[r++];
        while (sum >= target) {
            ans = Math.min(ans, r - l);
            sum -= nums[l++];
        }
    }
    return ans == (int) 1e5 + 10 ? 0 : ans;
}

变题三：可翻转部分数组

对于一个数组，求最大的子数组和，但是加了一个条件：可翻转一次任意子数组

例：数组[-1, 3, -5, 2, -1, 3]，翻转子数组[-5, 2, -1, 3]，最终原数组变成了[-1, 3, 3, -1, 2, -5]，此时最大的子数组和是 7

思路：分别求出[0 ... i]和[i+1 ... n-1]的最大子数组和leftSum, rightSum，leftSum, rightSum, leftSum + rightSum三者最大值即为翻转一次后最大子数组和

具体如下图所示：

由于该变题没有对应的题目，所以下面给出自己写的方法一和其他人写的方法二，以及测试代码


x
// 方法一
private int reverseSubArray(int[] nums) {
    int n = nums.length;
    int sum = 0, max = nums[0];
    // left[i] 表示 [0 ... i] 的最大子数组和，且至少要包含一个元素
    int[] left = new int[n];
    for (int i = 0; i < n; i++) {
        if (sum < 0) sum = nums[i];
        else sum += nums[i];
        max = Math.max(max, sum);
        left[i] = max;
    }
    sum = 0; max = 0;
    // right[i] 表示 [i-1 ... n-1] 的最大子数组和，可以一个元素也不包含，即为 0
    int[] right = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        right[i] = max;
        if (sum < 0) sum = nums[i];
        else sum += nums[i];
        max = Math.max(max, sum);
    }
    int ans = nums[0];
    for (int i = 0; i < n; i++) {
        // 取三者最大值
        int t = Math.max((left[i] + right[i]), Math.max(left[i], right[i]));
        ans = Math.max(ans, t);
    }
    return ans;
}
// 方法二
private int reverseSubArray2(int[] nums) {
    int n = nums.length;
    int[] sum = new int[n + 1];
    for (int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + nums[i - 1];
    int ans = 0;
    int[] mx = new int[n + 1];
    int[] mval = new int[n + 1];
    for (int i = 1, s = 0 ; i <= n ; i++) {
        s += nums[i - 1];
        if (s < 0) s = 0; // 求最大
        mx[i] = Math.max(mx[i - 1], s);
        mval[i] = Math.max(mval[i - 1], mx[i] - sum[i]);
        ans = Math.max(ans, sum[i] + mval[i - 1]);

    }
    return ans;
}
// 测试代码
public static void main(String[] args) {
    Random random = new Random();
    for (int k = 0; k < 1; k++) {
        int[] nums = new int[1000];
        for (int i = 0; i < 10; i++) nums[i] = random.nextInt(200000) - 100000;
        Solution solution = new Solution();
        int r1 = solution.f1(nums);
        int r2 = solution.f2(nums);
        if (r1 != r2) {
            System.out.println(Arrays.toString(nums));
            System.out.println((r1 == r2) + "-" + r1 + "-" + r2);
        }
    }
}

参考文章