Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

 

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Naive Way:因为在前面已经有了卖一次的代码，可以认为是交易两次和交易一次的比较，交易一次则采用之前的代码，交易两次则将视为将数组切割成两段，对每一段求一次交易的最大值，然后相加，着要求对每一位置作为切割点遍历。这样的算法复杂度是O(n^2)。

public int maxProfit(int[] prices) {
        if(prices.length <= 3){
            return subProfit(prices);
        }
        int max = 0;
        for(int i = 1;i < prices.length-1;i++){
            int sub1[] = new int[i];
            int sub2[] = new int[prices.length - i];
            for(int j = 0;j < i;j++)
                sub1[j] = prices[j];
            for(int j = i;j < prices.length;j++)
                sub2[j-i] = prices[j];
            int cur = subProfit(sub1)+subProfit(sub2);
            if(cur > max)
                max = cur;
        }
        return max;
    }
   
    private int subProfit(int[] prices) {
        if(prices.length == 0){return 0;}
        int opt = 0;
        int min = prices[0];
        for(int i = 1;i < prices.length;i++){
            if(prices[i] < min)
                min = prices[i];
            opt = Math.max(prices[i] - min, opt);
        }
        return opt;


还有一种想法就是感觉最多两次交易应该是跟最大值最小值有关的，找出第一个递减区间之后的最大值和第二大值，以及最小值和第二小值，应该可以通过分类讨论得到答案，但是这样做感觉就是数学方法而不是计算机方法。

那么比较正确的思路应该是扩展成k然后去想一个通用的解法。




Improved Way: 被告知有DP的解法，于是决定自己先试着做一下，那么走正常DP的思路。

opt[i][j] //表示在0~j天里最多交易i次能获得的最大利润
// base case
opt[0][j] = 0 (0 <= j <= n)  最多交易0次无利润
opt[i][0] = 0 (0 <= i <= k) 在0天里无法交易
// itreation
opt[i][j] = max(opt[i][j-1], max(opt[i-1][t] + p[j]-p[t+1]))  可能与j-1天相同，可能增加一次交易。

这样的做法算法复杂度是O(kn^2)，空间复杂度是O(nk)

private int maxProfit(int[] p, int k){
        int opt[][] = new int[k+1][p.length+1];
        // base case
        for(int i = 0;i <= k;i++)
            opt[i][0] = 0;
        for(int j = 0;j <= p.length;j++)
            opt[0][j] = 0;
        // iteration
        for(int i = 1;i <= k;i++){
            for(int j = 1;j <= p.length;j++){
                opt[i][j] = opt[i][j-1];
                for(int t = 0;t < j;t++)
                    opt[i][j] = Math.max(opt[i][j], opt[i-1][t] + p[j-1] - p[t]);
            }
        }
        return opt[k][p.length];
    }


看了一下Discuss上的解法才知道这个世界牛人真多，在https://oj.leetcode.com/discuss/15153/a-clean-dp-solution-which-generalizes-to-k-transactions上这位提出了将第三层循环写入第二层循环的做法，让人大呼过瘾。

我们可以注意到以上逻辑关键的一步：opt[i][j] = max(opt[i][j-1], max(opt[i-1][t] + p[j]-p[t+1]))
分解下来就是
如果第i天无交易，那么就是opt[i][j] = opt[i][j-1].
如果做出交易决定，就要看在之前t天里正好做i-1次交易， 加上p[j]-p[t+1]这最后一次交易，哪一个第t天带来最大利润。
后半部分 max(opt[i-1][t] + p[j-1] - p[t])
           =    max(p[j-1] + (opt[i-1][t] - p[t]))
           =    p[j-1] + max(opt[i-1][t] - p[t])
           =    p[j-1] + preMax
其中max(opt[i-1][t] - p[t])这一部分，我们是可以用O(1)的时间写进第二层循环中的。
因为t的范围是[0,j)， 也就是说，每一次 for(int j = 1;j <= p.length;j++) 的循环末尾，我们都将当前opt[i-1][j] - p[j] 与之前一次的 preMax相比较，就可以得到新的preMax给下一次循环用了。而preMax的初始值就是opt[i-1][0] - p[0]了，因为正好 for(int j = 1;j <= p.length;j++) 这个循环中j是从1开始的。

这样算法复杂度就成了O(kn)，对应这一题就是O(n)了。

private int maxProfit(int[] p, int k){
        int opt[][] = new int[k+1][p.length+1];
        // base case
        for(int i = 0;i <= k;i++)
            opt[i][0] = 0;
        for(int j = 0;j <= p.length;j++)
            opt[0][j] = 0;
        // iteration
        for(int i = 1;i <= k;i++){
            int preMax = opt[i-1][0] - p[0];
            for(int j = 1;j <= p.length;j++){
                opt[i][j] = opt[i][j-1];
                opt[i][j] = Math.max(opt[i][j], preMax + p[j-1]);
                preMax = Math.max(preMax, opt[i-1][j]-p[j]);
            }
        }
        return opt[k][p.length];
    }

忽然有种感觉，以前算法课上很多DP的题目貌似都是要内层循环要遍历之前所有的，说不定都可以这样把之前所有的这个循环套入内层循环中。