6/27, subarray 划分类，股票

所谓 “划分类” 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;
        }

Minimum Subarray

下面这两道 Max / Min Subarray 完全是一个套路： Kadane's Algorithm.

因为代码和思路看起来过于简单，比较容易忽略掉这题思路，还有正确性的分析。

比如 CodeForce 上这个帖子的另一种写法：

• 对于每一个位置 i ，我们维护

  • 当前 prefix sum；

  • subarray 最小 prefix sum

  • subarray 最大 prefix sum

• 其中每一个 subarray，都可以用 prefix sum 之间做减法获得。

• 即，这种迭代算法完整考虑了整个 array 中所有的 candidate subarray，因此保证了算法正确性。

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(ArrayList<Integer> nums) {
        // write your code
        int max = 0, min = Integer.MAX_VALUE;
        int prefixSum = 0;
        for(int i = 0; i < nums.size(); i++){
            prefixSum += nums.get(i);
            min = Math.min(min, prefixSum - max);
            max = Math.max(max, prefixSum);
        }

        return min;
    }
}

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 最优解。

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(ArrayList<Integer> nums) {
        // write your code
        int prevMin = 0;
        int cur = nums.get(0);
        int minRst = nums.get(0);
        for(int i = 1; i < nums.size(); i++){
            cur = Math.min(nums.get(i), prevMin + nums.get(i));
            minRst = Math.min(minRst, cur);
            prevMin = cur;
        }

        return minRst;
    }
}

Maximum Subarray

用区间和的思路：

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

        int max = Integer.MIN_VALUE, min = 0;
        int prefixSum = 0;
        for(int i = 0; i < nums.length; i++){
            prefixSum += nums[i];
            max = Math.max(max, prefixSum - min);
            min = Math.min(min, prefixSum);
        }

        return max;
    }
}

用 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;
    }
}

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) {
        int max = nums[0], min = nums[0];
        int rst = 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]);
            }
            rst = Math.max(rst, max);
        }

        return rst;
    }
}

Maximum Subarray II

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 {
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        // write your code
        if(nums == null || nums.size() == 0) return 0;

        int n = nums.size();

        // Maximum subarray value from left/right with n elements
        int[] left = new int[n];
        int[] right = new int[n];

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

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

        int rst = Integer.MIN_VALUE;

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

        return rst;
    }
}

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

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        // write your code
        if(nums == null || nums.size() == 0) return 0;

        int n = nums.size();

        // Maximum subarray value from left/right with n elements
        int[] left = new int[n];
        int[] right = new int[n];

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

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

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

        int rst = Integer.MIN_VALUE;

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

        return rst;
    }
}

Maximum Subarray III

optimal substructure 确定之后，最重要的是要思考循环的实现顺序：

是从 切分数 k 开始循环，还是从数组位置 i 开始循环？

首先思考这个性质：对于切割数为 j 的数组，如果其 size = i < j ，是无法得出正确结果的。换句话说，每次循环真正的正确起点，一定得至少是从 i = j 开始， i 受限于 j.

那么顺着这个思路，如果以 i 作为外循环，内循环 j 一定是在 [0, i] 区间内，并且 j <= k. 因此内循环需要两个条件：

• j <= k;

• j <= i;

对于任意指定 j ，需要做一个类似于我们之前计算 subarray I & II 时所需要的初始化，确保即使当前位置为负，作为以当前位置结尾的 localMax 依然选中此元素。因此先做一个 localMax[j - 1][j] = Integer.MIN_VALUE;

另一个需要着重注意的是，当 i = j ，即元素数 = 切分数时，即使当前元素为负，我们的 globalMax 也别无选择，必须以 localMax[i][j] 为准，采用当前元素。

public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: An integer denote to find k non-overlapping subarrays
     * @return: An integer denote the sum of max k non-overlapping subarrays
     */
    public int maxSubArray(int[] nums, int k) {
        // write your code here
        if(nums == null || nums.length == 0) return 0;

        int n = nums.length;


        int[][] localMax = new int[n + 1][k + 1];
        int[][] globalMax = new int[n + 1][k + 1];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k && j <= i; j++){
                localMax[j - 1][j] = Integer.MIN_VALUE;

                localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1])
                              + nums[i - 1];
                if(i == j) globalMax[i][j] = localMax[i][j];
                else globalMax[i][j] = Math.max(localMax[i][j], globalMax[i - 1][j]);
            }
        }

        return globalMax[n][k];
    }
}

这题的另一种循环写法，参照的九章答案。可以看到当循环内计算内容一致时，外循环的顺序是完全可以依据条件调换的，就像 Sparse Matrix Multiplication 一样。

public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: An integer denote to find k non-overlapping subarrays
     * @return: An integer denote the sum of max k non-overlapping subarrays
     */
    public int maxSubArray(int[] nums, int k) {
        // write your code here
        if(nums == null || nums.length == 0) return 0;

        int n = nums.length;


        int[][] localMax = new int[n + 1][k + 1];
        int[][] globalMax = new int[n + 1][k + 1];

        for(int j = 1; j <= k; j++){
            localMax[j - 1][j] = Integer.MIN_VALUE;
            for(int i = j; i <= n; i++){
                localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1])
                              + nums[i - 1];
                if(i == j) globalMax[i][j] = localMax[i][j];
                else globalMax[i][j] = Math.max(localMax[i][j], globalMax[i - 1][j]);
            }
        }

        return globalMax[n][k];
    }
}

Maximum Subarray Difference

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

于是这题变成了一个非常适合考察计算各种 local / global prefix sum 数组模板熟练度的问题。

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two
     *          Subarrays
     */
    public int maxDiffSubArrays(int[] nums) {
        // write your code here
                // write your code
        int n = nums.length;

        int[] leftMax = new int[n];
        int[] leftMin = new int[n];
        int[] rightMax = new int[n];
        int[] rightMin = 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;
        }

        prefixSum = 0;
        int localMax = 0;
        int globalMin = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            prefixSum += nums[i];
            globalMin = Math.min(globalMin, prefixSum - localMax);
            localMax = Math.max(localMax, prefixSum);
            leftMin[i] = globalMin;
        }

        prefixSum = 0;
        localMin = 0;
        globalMax = Integer.MIN_VALUE;
        for(int i = n - 1; i >= 0; i--){
            prefixSum += nums[i];
            globalMax = Math.max(globalMax, prefixSum - localMin);
            localMin = Math.min(localMin, prefixSum);
            rightMax[i] = globalMax;
        }

        prefixSum = 0;
        localMax = 0;
        globalMin = Integer.MAX_VALUE;
        for(int i = n - 1; i >= 0; i--){
            prefixSum += nums[i];
            globalMin = Math.min(globalMin, prefixSum - localMax);
            localMax = Math.max(localMax, prefixSum);
            rightMin[i] = globalMin;
        }

        int rst = Integer.MIN_VALUE;

        for(int i = 0; i < n - 1; i++){
            int ans = Math.max(Math.abs(leftMax[i] - rightMin[i + 1]),
                                Math.abs(leftMin[i] - rightMax[i + 1]));
            rst = Math.max(rst, ans);                    
        }

        return rst;
    }
}

Best Time to Buy and Sell Stock

很简单的问题，就当练手了。

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0) return 0;
        int min = prices[0];
        int maxProfit = 0;
        for(int i = 1; i < prices.length; i++){
            maxProfit = Math.max(maxProfit, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return maxProfit;
    }
}

Best Time to Buy and Sell Stock II

这个也基本是送分题，因为可以参与多次交易(unlimited)，只需要把每次的 increase 加在一起就可以了。

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0) return 0;
        int profit = 0;
        int min = prices[0];
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > min){
                profit += prices[i] - min;
            }
            min = prices[i];
        }

        return profit;
    }
}

Best Time to Buy and Sell Stock III

在透彻理解了 Maximum Subarray II 之后，这道题完全就是个套了马甲的简化版。

k 次交易 = k 个 non-overlapping subarray

以这个角度去想，无非就是从两个方向扫描，利用 localMin / localMax 与当前元素的差值，去构造从左边/右边扫的 dp 数组。

• left[i] : 从最左面到 i 所能获得的最大利益（单次交易）

• right[i] : 从 i 到最右面所能获得的最大利益（单次交易）

然后拼起来就好了。要注意的细节：

• 每个位置并不是非交易不可，需要用 0 来代表不做交易的情况；

• 不是非要做 “两次交易” 不可，因此 left[end] 作为一次交易的代表，也要考虑在内。

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1) return 0;
        int n = prices.length;

        int[] left = new int[n];
        int[] right = new int[n];

        int localMin = prices[0];
        int globalMax = Integer.MIN_VALUE;
        for(int i = 1; i < n; i++){
            globalMax = Math.max(globalMax, Math.max(0, prices[i] - localMin));
            localMin = Math.min(localMin, prices[i]);
            left[i] = globalMax;
        }

        int localMax = prices[n - 1];
        globalMax = Integer.MIN_VALUE;
        for(int i = n - 1; i >= 0; i--){
            globalMax = Math.max(globalMax, Math.max(0, localMax - prices[i]));
            localMax = Math.max(localMax, prices[i]);
            right[i] = globalMax;
        }

        int rst = 0;

        for(int i = 0; i < n - 1; i++){
            rst = Math.max(rst, left[i] + right[i + 1]);
        }
        // might be completely on left side;
        rst = Math.max(rst, left[n - 1]);

        return rst;
    }
}

Best Time to Buy and Sell Stock IV

延续了 subarray III 的优良传统，用 localMax 指代 “必须在当前位置结束” 来保证 local 子问题之间状态的连续性，用 globalMax 来记录状态之间可能的不连续性。

股票和 subarray 问题之间稍微有不同： subarray 里面初始化为 0 ，有时候元素为 -5 但是不得取，因此有些位置需要 Integer.MIN_VALUE 的初始化； 然而股票我可以选择不卖，初始的 0 就正好。

同样道理，股票中也不需要处理 subarray 问题中 i = j 时候必须强行拿当前元素，觉得亏我大不了不卖嘛，交易少于 k 也没事。

记得内循环条件是 j * 2 <= i + 1，而不是 j <= i / 2，否则报错，因为 index off-by-one 处理错了。

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices == null || prices.length == 0) return 0;

        int n = prices.length;

        if(k >= n / 2){
            int profit = 0;
            for(int i = 1; i < n; i++){
                int diff = prices[i] - prices[i - 1];
                if(diff > 0) profit += diff;
            }
            return profit;
        }

        int[][] localMax = new int[n][k + 1];
        int[][] globalMax = new int[n][k + 1];

        for(int i = 1; i < n; i++){
            int diff = prices[i] - prices[i - 1];
            for(int j = 1; j <= k && j * 2 <= i + 1; j++){
                localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1]) + diff;
                globalMax[i][j] = Math.max(localMax[i][j], globalMax[i - 1][j]);
            }
        }


        return globalMax[n - 1][k];
    }
}

Best Time to Buy and Sell Stock with cooldown

这个写法继承了原来股票问题的思路和 local 结构： 必须在第 i 天卖。 现在多了一种新操作"You do nothing"，就需要定义一个新数组。

考虑到股票 diff 的可拼接性质，sell[i] 可以直接由 sell[i - 1] + diff 构造而成；同时也可以由 do_nothing[i - 2] + diff 构造成，代表着上一次 sell 操作发生在 i - 3 事，i - 2 do_nothing, i - 1 买入， i 卖出的情形。

由这题我们可以发现，实际需要的 dp[] 数量是取决于操作数量的，要以“用当前操作结尾”来定义 localMax. 只不过在之前的问题中，因为买入卖出可以拼接，我们略去了 buy 的数组。

这题扩展开来的话，也可以扩展到 cooldown k 天，所依赖的状态，初始化，循环的起始位置会有变化而已。

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1) return 0;

        int n = prices.length;

        // max money in hand after each action
        int[] sell = new int[n];
        int[] donothing = new int[n];

        sell[1] = prices[1] - prices[0];

        for(int i = 2; i < n; i++){
            donothing[i] = Math.max(donothing[i - 1], sell[i - 1]);
            sell[i] = prices[i] - prices[i - 1] + Math.max(sell[i - 1], donothing[i - 2]);
        }

        return Math.max(sell[n - 1], donothing[n - 1]);
    }
}

居然有人用状态机去写这类题， 好巧妙啊。

https://leetcode.com/discuss/72030/share-my-dp-solution-by-state-machine-thinking

在整个交易过程中，我们只可能处于如上图所示的三种状态中。

这个解法的要点是，每个 state 的 in-degree 代表能到达当前 state 的所有可能操作。

• s0 可能由上一次的 s0，或上一次的 s2 卖掉而来；

• s1 可能由上一次的 s1，或者上一次的 s0 买入而来；

• s2 只可能由 s1 的卖出而来。

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n <= 1) return 0;
        int[] s0 = new int[n];
        int[] s1 = new int[n];
        int[] s2 = new int[n];

        s0[0] = 0;
        s1[0] = -prices[0];
        s2[0] = Integer.MIN_VALUE;

        for (int i = 1; i < n; i++) {
            s0[i] = Math.max(s0[i - 1], s2[i - 1]);
            s1[i] = Math.max(s1[i - 1], s0[i - 1] - prices[i]);
            s2[i] = s1[i - 1] + prices[i];
        }

        return Math.max(s0[n - 1], s2[n - 1]);
    }
}