买卖股票最佳时机--- IV

假定最大交易次数为k次，我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。

transition equation:
diff = prices[i] - prices[i - 1];
local[i][j] = Max(global[i - 1][j - 1] + diff, local[i - 1][j] + diff);


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


代码如下:

1. /*
   
2. * j -- max # of transactions; i --- # of days;
   
3. *  local[i][j] -- profit achieved when selling at last day;
   
4. *  global[i][j] --- profit achieved at all situations;
   
5. *  transition equation:
   
6. *          local[i][j] =  max(local[i - 1][j], global[i - 1][j - 1]) + diff;
   
7. *      (merge with previous transactions or NOT)
   
8. *      global[i][j] = max(local[i][j], global[i - 1][j]);
   
9. */
   
10. public class SolutionIV {
    
11.     public int maxProfit(int k, int[] prices) {
    
12.             int N = prices.length;
    
13.             if (k >= N)
    
14.                     return simpleMaxProfit(prices);
    
15.         int[] local = new int[k + 1], global = new int[k + 1];
    
16.         int[] prevLocal = new int[k + 1], prevGlobal = new int[k + 1];
    
17.         for (int i = 1; i < N; ++i) {
    
18.                 prevLocal = local; prevGlobal = global;
    
19.                 local = new int[k + 1]; global = new int[k + 1];
    
20.                 int diff = prices[i] - prices[i - 1];
    
21.                 for (int j = 1; j <= k; ++j) {
    
22.                         local[j] = Math.max(prevGlobal[j - 1], prevLocal[j]) + diff;
    
23.                         global[j] = Math.max(local[j], prevGlobal[j]);
    
24.                 }
    
25.         }
    
26.         return global[k];
    
27.     }
    
28.     int simpleMaxProfit(int[] prices) {
    
29.             int N = prices.length;
    
30.             if (N <= 1)
    
31.                     return 0;
    
32.             int sum = 0;
    
33.             for (int i = 1; i < N; i++) {
    
34.                     int diff = prices[i] - prices[i - 1];
    
35.                     if (diff > 0)
    
36.                             sum += diff;
    
37.             }
    
38.             return sum;
    
39.     }
    
40.     public static void main(String[] args) {
    
41.         SolutionIV sol = new SolutionIV();
    
42.         int[] nums = {4, 6, 1, 1, 4, 2, 5};
    
43.         System.out.println(sol.maxProfit(2, nums));
    
44.     }
    
45. }
    

复制代码

技术贴，先顶了

恩， 这题这个套路 用矩阵实现kadane's algorithm ，还可以用在 max subarray III 和copy books 的DP解法上。

不过股票IV这题有个线性解，我至今没有很好的理解, 在这里歪个楼，有人想讨论么？ 也许咱们讨论出的凑一块没准能懂。。。
https://discuss.leetcode.com/topic/9522/c-solution-with-o-n-klgn-time-using-max-heap-and-stack/24
https://maskray.me/blog/2015-03-27-leetcode-best-time-to-buy-and-sell-stock-iv

John.Tan 发表于 2016-12-28 16:01
恩， 这题这个套路 用矩阵实现kadane's algorithm ，还可以用在 max subarray III 和copy books 的DP解法上 ...

那个n + k * log(n)解法是很好，但是好复杂~~~ 感觉面试时肯定不能bug-free写出来

是蛮复杂的，  思路就是找到所有 相邻的local valley/peak, 然后把这个 {v, p} pairs 按建一个vector, 从vector 中找出前k大的不重叠的落差。。。  具体实现这个找前k大不重叠落差的代码我就傻逼了。。。。s