前缀和，划分类DP

所谓 “划分类” DP，是指给定原数组之后，将其划分为 k 个子数组，使其 sum / product 最大 / 最小的 DP 类问题。

而这类问题的 optimal substructure 是，对于给定区间的globalMax，其最优解一定由所属区间内的 localMax 区间组成，可能不连续。 以“必须以当前结尾” 来保证 local 子问题之间的连续性；用 global 来记录最优解之间可能的不连续性。

划分类DP 与 区间类DP 主要区别在于，我们只取其中 k 段，而中间部分可以留空；而区间类 DP 子问题之间是连贯而不留空的。区间类 DP 是记忆化的 divide & conquer, 划分类 DP 则是不连续 subarray 的组合，不同于区间类 DP 每一个区间都要考虑与计算，划分类DP 很多元素和子区间是可以忽略的，有贪心法的思想在里面，因此也依赖于正确的 local / global 结构来保证算法的正确性。

Kadane's Algorithm 相比 prefix sum 的特点是，必须要以 nums[0] 做初始化，从 index = 1 开始搜，优点是在处理 prefix product 的时候更容易处理好“-5” 和 “0” 的情况。

这类靠 prefix sum/product 的 subarray 问题，要注意好对于每一个子问题的 local / global 最优解结构，其中 local 解都是“以当前结尾 && 连续”，而 global 未必。

Prefix sum 数组的 local / global 通用模板，求 min / max 皆可，使用时需要注意初始条件以及顺序。

    int[] leftMax = new int[n];
    int prefixSum = 0;
    // 代表从起始位置开始，值最小的连续和数组
    int localMin = 0;
    int globalMax = Integer.MIN_VALUE;
    for(int i = 0; i < n; i++){
        prefixSum += nums[i];
        globalMax = Math.max(globalMax, prefixSum - localMin);
        localMin = Math.min(localMin, prefixSum);

        leftMax[i] = globalMax;
    }

53. Maximum Subarray

Minimum Subarray

这两道题是一样的，就是改一下最大最小。

首先从这道题做一个入门，了解前缀和最基本的思想。

有正有负的一个数组，求的是一段最大连续子数组。

前缀和：sum[i] = Σ{nums[0 - i]}

到第i个数为止，前i个数的和为sum[i]。

原数组：-2，2，-3，4，-1，2，1

前缀和：-2，0，-3，1， 0，2，3

求i - j的区间的时候，求第i个数到第j个数的和：sum[j] - sum[i - 1]

所以为了找到最大的连续子数组，我们必须维护一个记录最小前缀和的变量。这样用最大前缀和减最小前缀和就是最大的连续子数组段。

所有与subarray相关的问题，都要想到前缀和的方法。

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int sum = 0;
        int max = Integer.MIN_VALUE;
        int minSum = 0;

        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
        }
        return max;
    }
}

两种初始化的方法。

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int sum = nums[0];
        int max = nums[0];
        int minSum = nums[0];

        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
        }
        return max;
    }
}

说一下前面提到的Kadane's Algorithm

Kadane's Algorithm其实是在维护一个 sliding window，不过每个迭代的时候，在考虑以当前元素为新起点之余，又砍去了之前的部分。

input : [-1,5,6,-1,-2,4]

• iter0: max = -1, prev = sum[-1];
• iter1: max = 5, prev = sum[5];
• iter2: max = 11, prev = sum[5,6];
• iter3: max = 11, prev = sum[5,6,-1];
• iter4: max = 11, prev = sum[5,6,-1,-2];
• iter5: max = 12, prev = sum[5,6,-1,-2,4]

可以看到，在 kadane's algorithm 中，我们保存的这个 prevMin 始终是连续的，起点不一定是哪，但是终点一定是 current，是一个 local 最优解。我们每次迭代，用 local 最优解去更新 global 最优解。

这道题用 Kadane's Algorithm 的解法:

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int cur = nums[0];
        int max = nums[0];

        for (int i = 1; i < nums.length; ++i) {
            cur = Math.max(nums[i], cur + nums[i]);
            max = Math.max(max, cur);
        }
        return max;
    }
}

152. Maximum Product Subarray

L 家面经题。

相比较 prefix sum 的问题，操作改成乘法之后有几个不同的地方需要处理：

• 负号。遇到负号时，原本的 min / max 会直接反转。最优解可能是有一系列正数相乘而来，但也可能是一系列正数中带着偶数个数的负数。
  • 保存以当前元素截止的 min / max subarray （保证连续性），遇到负数时调换相乘。

• 加法操作遇到 0 是无所谓的，乘法操作却会导致直接切断 prefix product.
  • 每个位置的 max / min subarray 同时考虑当前元素，正确处理 0 之余保证连续性。

其实这个做法与其说像 prefix product ，不如说更像 Kadane's Algorithm.可以看到这个算法可以有效免疫各种切断的情况，只维护到当前位置结尾的 max / min subarray 结果就可以了。

在这里面，min/max 是连续的，local 以 i 结尾的； rst 是 global 非连续的。

• 前缀积在这题上没用，所有的都是 localMin / localMax，迭代更新。

• 不能用 val = 1 来做初始化，要用 nums[0]；

• nums[i] 为负时，要多开个临时变量，不然会覆盖掉下一行需要的值

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int max = nums[0];
        int min = nums[0];
        int result = nums[0];

        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > 0) {
                max = Math.max(nums[i], max * nums[i]);
                min = Math.min(nums[i], min * nums[i]);
            } else {
                int oldMax = max;
                max = Math.max(nums[i], min * nums[i]);
                min = Math.min(nums[i], oldMax * nums[i]);
            }
            result = Math.max(result, max);
        }
        return result;
    }
}

Kadane's Algorithm 的精髓就在于每次都是最大/最小(前缀和/积) 和 当前的nums[i]相比。就像最前面写的，通过local子问题的解来得出global的解。

Maximum Subarray II

Maximum Subarray I 只是开胃菜的话，这道题就开始比较认真考察如何利用 prefix sum 做 DP 解决 subarray sum 类问题了。

这次光用 local 变量更新然后返回 global 最优还不够，我们需要保存对于每一个子问题的 global 最优（可能并不以当前位置结尾），用于后面的左右两边全局查询。

我们需要利用 prefix sum 数组，定义两个 dp[]

• left[i] 代表从最左边到 i 位置所能取得的最大 subarray sum;

• right[i] 代表从最右边到 i 位置所能取得的最大 subarray sum;

• 两个数组都是 global 解。

• 每次迭代的变量 minSum 和 prefixSum 是相对于每个位置的 local 解。

这样对于每一个位置 i ，我们都可以用 left[] 和 right[] 的子数组把最优解拼接出来。

public class Solution {
    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) return 0;

        int n = nums.size();
        int[] left = new int[n];
        int[] right = new int[n];

        int sum = nums.get(0);
        int max = nums.get(0);
        int min = nums.get(0);

        for (int i = 0; i < n; ++i) {
            sum += nums.get(i);
            max = Math.max(max, sum - min);
            min = Math.min(min, sum);
            left[i] = max;
        }

        sum = nums.get(n - 1);
        max = nums.get(n - 1);
        min = nums.get(n - 1);

        for (int i = n - 1; i >= 0; --i) {
            sum += nums.get(i);
            max = Math.max(max, sum - min);
            min = Math.min(min, sum);
            right[i] = max;
        }
        max = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; ++i) {
            max = Math.max(max, left[i] + right[i + 1]);
        }
        return max;
    }
}

还可以这么理解，我们要在一个数组中找不相交的两个子数组，也就是要找出一个分割线，使得左右两边的子数组和最大，因为我们要返回的是子数组的和。所以我们从左至右，再从右至左，记录下所有位置上可能的最大和最小，最后再用一个for loop去找那条分割线在哪，但返回只需要返回一个最大的sum就行了。

同样的思路，用 Kadane's Algorithm 就要注意初始化问题，不然无法正确处理 array 两端的负数。

public class Solution {
    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) return 0;

        int n = nums.size();
        int[] left = new int[n];
        int[] right = new int[n];

        int max = nums.get(0);
        int cur = nums.get(0);
        left[0] = nums.get(0);

        for (int i = 1; i < n; ++i) {
            cur = Math.max(nums.get(i), cur + nums.get(i));
            max = Math.max(max, cur);
            left[i] = max; 
        }

        max = nums.get(n - 1);
        cur = nums.get(n - 1);
        right[n - 1] = nums.get(n - 1);

        for (int i = n - 2; i >= 0; --i) {
            cur = Math.max(nums.get(i), cur + nums.get(i));
            max = Math.max(max, cur);
            right[i] = max;
        }

        max = Integer.MIN_VALUE;

        for (int i = 0; i < n - 1; ++i) {
            max = Math.max(max, left[i] + right[i + 1]);
        }
        return max;
    }
}

Maximum Subarray III

Maximum Subarray Difference

这题和之前求 maximum non-overlap subarrays 的思路基本一致，只不过要求的数组变成了四个：leftMax, leftMin, rightMax 和 rightMin

直接写 Kadane's Algorithm 方法的代码了，因为我觉得Kadane更简洁一点。

需要注意的是在用Kadane的时候一定记得left和right数组的初始化。因为我们是从index = 1 或 n - 2的地方开始for loop的。

public class Solution {
    public int maxDiffSubArrays(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int n = nums.length;
        int[] lmin = new int[n];
        int[] rmin = new int[n];
        int[] lmax = new int[n];
        int[] rmax = new int[n];

        int curMax = nums[0];
        int curMin = nums[0];
        int max = nums[0];
        int min = nums[0];
        lmin[0] = nums[0];
        lmax[0] = nums[0];

        for (int i = 1; i < n; ++i) {
            curMax = Math.max(nums[i], curMax + nums[i]);
            curMin = Math.min(nums[i], curMin + nums[i]);
            max = Math.max(max, curMax);
            min = Math.min(min, curMin);
            lmax[i] = max;
            lmin[i] = min;
        }

        curMax = nums[n - 1];
        curMin = nums[n - 1];
        max = nums[n - 1];
        min = nums[n - 1];
        rmin[n - 1] = nums[n - 1];
        rmax[n - 1] = nums[n - 1];

        for (int i = n - 2; i >= 0; --i) {
            curMax = Math.max(nums[i], curMax + nums[i]);
            curMin = Math.min(nums[i], curMin + nums[i]);
            max = Math.max(max, curMax);
            min = Math.min(min, curMin);
            rmax[i] = max;
            rmin[i] = min;
        }

        int diff = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; ++i) {
            diff = Math.max(diff, Math.max(Math.abs(lmax[i] - rmin[i + 1]), Math.abs(lmin[i] - rmax[i + 1])));
        }
        return diff;
    }
}

238. Product of Array Except Self

一道前缀积的题，蛮有意思。

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];

        int len = nums.length;
        int[] left = new int[len + 1];
        int[] right = new int[len + 1];

        left[0] = 1;
        right[len] = 1;
        for (int i = 0; i < len; ++i) {
            left[i + 1] = left[i] * nums[i];
        }
        for (int i = len - 1; i >= 0; --i) {
            right[i] = right[i + 1] * nums[i];
        }
        int[] result = new int[len];
        for (int i = 0; i < len; ++i) {
            result[i] = left[i] * right[i + 1];
        }
        return result;
    }
}