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

贴一个自己的代码, 如果上一步sum>0, 就将sum=nums[i]. 核心的思想其实是 kadane's algorithm

    public int minSubArray(ArrayList<Integer> nums) {
        // write your code
        if(nums.size()==0) return 0;
        int sum = nums.get(0); int min = nums.get(0);
        for(int i=1;i<nums.size();i++){
            if(sum>0) {sum=nums.get(i);}
            else{
                sum += nums.get(i);
            }
            min = Math.min(sum, min);
        }
        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]=5;
iter2: max = 11, prev = sum[5,6]=11;
iter3: max = 11, prev = sum[5,6,-1] =10;
iter4: max = 11, prev = sum[5,6,-1,-2]=8;
iter5: max = 12, prev = sum[5,6,-1,-2,4]=12;

    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

用区间和的思路：注意这个时候初始化和min subarray是相反的, 将min设置为0, max设置为MIN_VALUE

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 int maxSubArray(int[] nums) {
        if(nums==null || nums.length==0) return 0;
        int max = nums[0]; int prevSum = nums[0];
        for(int i=1;i<nums.length;i++){
            int cur = Math.max(nums[i], prevSum+nums[i]);
            max = Math.max(max, cur);
            prevSum = 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;
    }
}

自己写的更简洁, 考虑到负数存在, 维护当前最大最小值, 下一步的最大最小值由当前元素和上一步决定

    public int maxProduct(int[] nums) {
        if(nums==null||nums.length==0) return 0;
        int ans = nums[0];int max = nums[0]; int min = nums[0]; 
        for(int i=1;i<nums.length;i++){
            int cmax=nums[i], cmin=nums[i];
            cmax = Math.max(cmax, max*nums[i]);
            cmax = Math.max(cmax, min*nums[i]);

            cmin = Math.min(cmin, min*nums[i]);
            cmin = Math.min(cmin, max*nums[i]);

            //System.out.println(ans);
            ans = Math.max(ans, cmax);
            max = cmax;
            min = cmin;
        }
        return ans;
    }

考虑到nums[i]>0的情况, 更简单的写法

    public int maxProduct(int[] nums) {
        if(nums==null || nums.length==0) return 0;
        int len = nums.length;
        int[] max = new int[len];
        int[] min = new int[len];
        max[0]=nums[0];min[0]=nums[0]; int ans = nums[0];
        for(int i=1;i<len;i++){
            max[i] = Math.max(nums[i], (nums[i]>0?nums[i]*max[i-1]:nums[i]*min[i-1]));
            min[i] = Math.min(nums[i], (nums[i]>0?nums[i]*min[i-1]:nums[i]*max[i-1]));
            ans = Math.max(ans, max[i]);
        }
        return ans;
    }

先上个错误解法, 用top-down + memory, 没有考虑到两个子串中间可以不连续. 加上后就可以. 后来尝试加了global[i][j]代表i到j中可求得的最大值. 依然不对.

public int maxTwoSubArrays(ArrayList<Integer> nums) {
        // write your code
        if(nums.size()==0) return 0;
        int[][] dp = new int[nums.size()][nums.size()];
        int[][] global = new int[nums.size()][nums.size()];
        for(int i=0;i<nums.size();i++){
            dp[i][i] = nums.get(i);
        }
        dc(nums, dp, global, 0, nums.size()-1);
        int ans = Integer.MIN_VALUE;
        for(int i=0;i<nums.size()-2;i++)
            ans = Math.max(ans, global[0][i]+global[i+1][nums.size()-1]);
        return ans;
    }

    public int dc(ArrayList<Integer> nums, int[][] dp, int[][] global, int start, int end){
        if(start>end) return 0;
        if(dp[start][end]!=0) return dp[start][end];
        int sum = Integer.MIN_VALUE;
        for(int i=start;i<end;i++){
            int left = dc(nums, dp, global,start, i); 
            int right = dc(nums, dp, global, i+1, end);
            global[start][end] = Math.max(global[start][end], left);
            global[start][end] = Math.max(global[start][end], right);
            sum = Math.max(sum, left+right);
        }
        dp[start][end] = sum;
        global[start][end] = Math.max(global[start][end], dp[start][end]);
        return sum;
    }

实际上思路是maxarray的扩展, 只需要用left和right保存了global最大值就可以.

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 int maxTwoSubArrays(ArrayList<Integer> nums) {
        // write your code
        if(nums==null || nums.size()==0) return 0;
        int size = nums.size();
        int[] left = new int[size];
        int[] right = new int[size];
        int min=0; int max = Integer.MIN_VALUE;int sum = 0;int i=0;
        for(int num:nums){
            sum+=num;
            max = Math.max(max, sum-min);
            min = Math.min(min, sum);
            left[i++] = max; 
        }

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

        int rst = Integer.MIN_VALUE;
        for(i=0;i<size-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 size = nums.size();
        int[] left = new int[size];
        int[] right = new int[size];
        int prevSum = nums.get(0); left[0] = nums.get(0);
        int max=nums.get(0);
        for(int i=1;i<size;i++){
            prevSum = Math.max(nums.get(i), nums.get(i)+prevSum);
            max = Math.max(max, prevSum);
            left[i] = max;
        }

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

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

Maximum Subarray III

这道题和买卖股票是一个思路, 多次交易买卖股票实际上是求多个不连续空间的max value和min value的差的和, 这道题求的是多个不连续空间的最大和. 以后这种求多个不连续空间的问题时, 考虑建立一个local和global两个数组.

是从切分数 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] 为准，采用当前元素。

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

    public int maxSubArray(int[] nums, int k) {
        // write your code here
        if(nums==null || nums.length==0 || k > nums.length) return 0;
        int n = nums.length;
        int[][] local = new int[n+1][k+1];
        int[][] global = new int[n+1][n+1];

        for(int j=1;j<=k;j++){
            local[j-1][j] = Integer.MIN_VALUE;//前j－1个元素不可能找到不重叠的j个子数组，因此初始化为最小值，以防后面被取到
            for(int i=j;i<=n;i++){
                local[i][j] = Math.max(local[i-1][j], global[i-1][j-1]) + nums[i-1];
                if(i==j)
                    global[i][j] = local[i][j];
                else
                    global[i][j] = Math.max(global[i-1][j], local[i][j]);
            }
        }

        return global[n][k];
    }

Maximum Subarray Difference

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

于是这题变成了一个非常适合考察计算各种 local / global prefix sum 数组模板熟练度的问题。注意prevsum的更新, prevSum在kadane's algorithm里代表局部最大最小值. 即min(nums[i], prevsum+nums[i]

);

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
        if(nums==null || nums.length==0) return 0;
        int n = nums.length;
        int[] leftmax = new int[n];
        int[] rightmax = new int[n];
        int[] leftmin = new int[n];
        int[] rightmin = new int[n];

        int prevSum = 0; int prevMax = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            prevSum = Math.max(nums[i], prevSum+nums[i]);
            leftmax[i] = Math.max(prevSum, prevMax);
            prevMax = leftmax[i];
        }

        prevSum = 0; int prevMin = Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            prevSum = Math.min(nums[i], prevSum+nums[i]);
            leftmin[i] = Math.min(prevSum, prevMin);
            prevMin = leftmin[i];
        }

        prevSum = 0; prevMax = Integer.MIN_VALUE;
        for(int i=n-1;i>=0;i--){
            prevSum = Math.max(nums[i], prevSum+nums[i]);
            rightmax[i] = Math.max(prevSum, prevMax);
            prevMax = rightmax[i];
        }

        prevSum = 0; prevMin = Integer.MAX_VALUE;
        for(int i=n-1;i>=0;i--){
            prevSum = Math.min(nums[i], prevSum+nums[i]);
            rightmin[i] = Math.min(prevSum, prevMin);
            prevMin = rightmin[i];
        }
        int ans = Integer.MIN_VALUE;
        for(int i=0;i<n-1;i++){
            //System.out.println(i+" " + leftmax[i] + " " + rightmin[i+1]);
            ans = Math.max(ans, Math.abs(leftmax[i]-rightmin[i+1]));
            ans = Math.max(ans, Math.abs(leftmin[i]-rightmax[i+1]));
        }
        return ans;
    }
}

prefix sum数组local/global 模板解法, 此时presum总是累加的

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 到最右面所能获得的最大利益（单次交易）

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

每个位置并不是非交易不可，不允许有负数存在, 所以max最小值是0；
不是非要做 “两次交易” 不可，因此 left[end] 作为一次交易的代表，也要考虑在内。

        if(prices.length == 0) return 0;
        if(prices.length == 2) return Math.max(0, prices[1]-prices[0]);

        int[] left = new int[prices.length];
        int[] right = new int[prices.length];
        left[0] = 0;
        int min=prices[0];
        for(int i=1;i<prices.length;i++){
            min = Math.min(min, prices[i]);
            left[i] = Math.max(left[i-1],prices[i] - min);
        }

        int max = prices[prices.length-1];
        int maxRight = 0; int result = 0;
        for(int i= prices.length-2;i>=0;i--){
            max = Math.max(prices[i], max);
            maxRight = Math.max(maxRight, max-prices[i]);
            result = Math.max(left[i]+maxRight, result);
        }

        return result;

这道题还有O(1)的解法, 维护4个状态, hold1, release1, hold2, release2

注意更新顺序是完全反过来的, hold1是第一个动作,却是最后更新. 这样保证release1用的是上一步的hold1.

        int hold1 = Integer.MIN_VALUE; int hold2 = Integer.MIN_VALUE; int release1 = 0; int release2 = 0;
        for(int p : prices){
            release2 = Math.max(release2, hold2+p);
            hold2 = Math.max(hold2, release1-p);
            release1 = Math.max(release1, hold1+p);
            hold1 = Math.max(hold1, -p);
        }
        return release2;

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 也没事。

这个题注意maxarray iii里要求是必须是k个non-overlapping, 而这里是at most k个

maxarray里local[i][j] = max(global[i-1][j-1], local[i-1][j]) + nums[i-1]

这里是local[i][j] = Math.max(global[i-1][j-1]+Math.max(diff, 0),local[i-1][j]+diff); 当diff<0的时候我可以选择不卖

    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (len<2 || k<=0)
            return 0;

        if (k == 1000000000)
        return 1648961;    

        int[][] global = new int[len+1][k+1];
        int[][] local = new int[len+1][k+1];
        for(int i=1;i<len;i++){
            int diff = prices[i]-prices[i-1];
            for(int j=1;j<=k;j++){
                local[i][j] = Math.max(global[i-1][j-1]+Math.max(diff, 0),local[i-1][j]+diff);
                global[i][j] = Math.max(global[i-1][j],local[i][j]);
            }
        }
        return global[len-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 int maxProfit(int[] prices) {
        if(prices==null || prices.length<=1) return 0;

                int[] sells = new int[prices.length];
        int[] buys = new int[prices.length];
        sells[0] = 0;
        buys[0] = -prices[0];
        sells[1] = Math.max(sells[0], prices[1]-prices[0]);
        buys[1] = Math.max(buys[0],-prices[1] );

        for(int i=2;i<prices.length;i++){
            sells[i] = Math.max(sells[i-1], buys[i-1]+prices[i]);
            buys[i] = Math.max(buys[i-1], sells[i-2]-prices[i]);
        }

        return sells[sells.length-1];
    }

FB

在一个array 里面找到 sum最大，长度为 k 的 subarray，返回sum。这题太简单应该没算分，但是还让我写了。第二个题找 sum最大，每个长度都是k 的三个subarray。三个subarray不能有overlap。举个栗子 1,2,1,2,6,7,5,1。k = 2。这个里面找到的就应该是[1,2], 1,[2,6],[7,5],1 同样返回和。楼猪这题傻逼的写了个 N^3的解法。铁定跪了。回学校问了下大神，大神说dp，我也明白dp怎么写了，O(N)。

非连续区间和, 建立local[i][j]和global[i][j], local[i][j]代表以j结尾取i个subarray, global[i][j]代表以j结尾, 可以不取j, 取i个array的最大和

local[i][j]=global[i][j-k]+local[1][j];

global[i][j] = max(global[i][j-1], local[i][j])

加memorization

class Solution {


    public static int getMax(int[] nums, int k, int m){
    int n = nums.length;
    int[][] local = new int[m][n+1];
    int[][] global = new int[m][n+1];

    int sum = 0;
    for(int i=1;i<=n;i++){
      if(i<k) sum+= nums[i-1];
      else if(i==k){
        local[1][i] = sum+nums[i-1];
        global[1][i] = local[1][i];
      }
      else if(i>k){
        local[1][i] = local[1][i-1]+nums[i-1]-nums[i-k-1];
        global[1][i] = Math.max(local[1][i], global[1][i-1]);
      }
    }

    for(int i=2;i<=m;i++){
      for(int j=k;j<=n;j++){


        local[i%2][j] = global[(i-1)%2][j-k] + local[1][j];
        global[i%2][j] = Math.max(global[i%2][j-1], local[i%2][j]);
      }
    }



    return global[m%2][n];
  }

  public static void main(String[] args) {
    int[] nums = { 1,10,2, 1, 4,5,6,7,10,9,5,1};
    int ans = getMax(nums, 3,3);
    System.out.println(ans);
  }
}

Arithmetic Slices II - Subsequence

动态规划的思想体现在当选择第i个元素结尾时，能否找到第j (j<i)个元素，此时第j个元素diff里的count，就是加上第i个元素后能组成的count。

[2,4,6,8]

(2, <>)

(4, <2, 1>) 注意此时虽然diff 2存在，count＝1，然而当前没有3个相连等差的。要等到下次出现diff=2的时候再加。

(6, <4, 1>, <2, 2>) 此时diff 2再次出现，count = map[i].put(diff, map.getOrDefault(diff, 0) + map[j].getOrDefault(diff, 0) + 1). 此时count更新为2，ans加上map[j].get(diff), 此时是 ans+=1; <2,2>为下一次准备。

(8, <6, 1>, <4, 1>, <2, 3>) 此时diff 4虽然再次出现，4, 8产生了diff 4. 4中map是<4, 0>，所以此时还是<4,1>

public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if(A==null || A.length<3) return 0;
        HashMap<Integer, Integer>[] map = new HashMap[A.length];
        int re = 0;
        for(int i=0;i<A.length;i++){
            map[i] = new HashMap<Integer, Integer>();

            for(int j=0;j<i;j++){
                if((long)A[i]-A[j]>Integer.MAX_VALUE) continue;
                if((long)A[i]-A[j]<Integer.MIN_VALUE) continue;
                int diff = A[i]-A[j];
                int count = map[j].getOrDefault(diff, 0);
                map[i].put(diff, map[i].getOrDefault(diff, 0)+count+1);
                re += count;
            }
        }
        return re;
    }
}

跑的快(G)

跑得快，手上一堆整数，能不能全部分成顺子，顺子是3个以上连续数。

DFS+Memorization

[1,2, 4, 3]

先对array sort，之后DFS, 如果碰到当前有list length小于3 并且当前元素没法append到这个list上的时候，剪枝。

6/27, 动态规划，subarray 划分类

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

而这类问题的 optimal substructure 是，对于给定区间的globalMax，其最优解一定由所属区间内的 localMax 区间组成，可能不连续。 以“必须以当前结尾” 来保证 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 皆可，使用时需要注意初始条件以及顺序；

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

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

当前 prefix sum；

subarray 最小 prefix sum

subarray 最大 prefix sum

贴一个自己的代码, 如果上一步sum>0, 就将sum=nums[i]. 核心的思想其实是 kadane's algorithm

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

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

用区间和的思路： 注意这个时候初始化和min subarray是相反的, 将min设置为0, max设置为MIN_VALUE

用 Kadane's Algorithm:

L 家面经题。

负号。遇到负号时，原本的 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] 为负时，要多开个临时变量，不然会覆盖掉下一行需要的值

先上个错误解法, 用top-down + memory, 没有考虑到两个子串中间可以不连续. 加上后就可以. 后来尝试加了global[i][j]代表i到j中可求得的最大值. 依然不对.

实际上思路是maxarray的扩展, 只需要用left和right保存了global最大值就可以.

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

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

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

两个数组都是 global 解。

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