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]);
    }
}

results matching ""

    No results matching ""