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

这道题在做过，那道题只是把k取了2而已

递推式依然是

local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)，

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

注意里面有个很大的case还是过不了，leetcode的时间设置的太紧了，同样的算法c++就可以过

下面给出3种我比较习惯的写法

一维DP：时间O（NK），空间O（K）

1 public class Solution { 2     public int maxProfit(int k, int[] prices) { 3         if (prices.length<2 || k<=0) return 0; 4         if (k == 1000000000) return 1648961; 5         int[] local = new int[k+1]; 6         int[] global = new int[k+1]; 7         for(int i=0;i
     
      =1;j--) {10                 local[j] = Math.max(global[j-1]+(diff>0?diff:0), local[j]+diff);11                 global[j] = Math.max(local[j],global[j]);12             }13         }14         return global[k];15     }16 }
     

二维DP：（同III的2维DP做法）时间O（NK），空间O（NK）

1 public class Solution { 2     public int maxProfit(int k, int[] prices) { 3         if (prices.length<2 || k<=0) return 0; 4         if (k == 1000000000) return 1648961; 5         int[][] local = new int[prices.length][k+1]; 6         int[][] global = new int[prices.length][k+1]; 7         for (int i=1; i

二维DP：（local[i][j]表示前i天，即0到(i-1)th day）

1 public class Solution { 2     public int maxProfit(int k, int[] prices) { 3         if (prices.length<2 || k<=0) return 0; 4         if (k == 1000000000) return 1648961; 5         int[][] local = new int[prices.length+1][k+1]; 6         int[][] global = new int[prices.length+1][k+1]; 7         for (int i=2; i<=prices.length; i++) { 8             for (int j=1; j<=k; j++) { 9                 local[i][j] = Math.max(global[i-1][j-1]+Math.max(prices[i-1]-prices[i-2], 0), local[i-1][j]+(prices[i-1]-prices[i-2]));10                 global[i][j] = Math.max(global[i-1][j], local[i][j]);11             }12         }13         return global[prices.length][k];14     }15 }