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;
}
下面这两道 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;
}
}用区间和的思路：
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;
}
}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;
}
}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;
}
}
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 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;
}
}很简单的问题，就当练手了。
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;
}
}这个也基本是送分题，因为可以参与多次交易(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;
}
}在透彻理解了 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;
}
}延续了 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];
}
}这个写法继承了原来股票问题的思路和 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]);
}
}Last updated
Was this helpful?