原题链接在这里：

题目： 

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 two transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 

题解：

本题是的进阶版。思路也很相似，仍旧是维护一个全局最优，一个局部最优。

这里最多可以进行k次交易，就是然后本题把k变成2即可。

全局最优global是到达第i天可以最多进行j次交易的利润是多少，局部最优local是必须在第i天进行最后一次交易的利润。

先更新局部最优:

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

diff是今天与昨天的差价, global[i-1][j-1] + max(diff,0)是指到第i-1天最多进行j-1次交易时的利润，加上进天得最后一次交易。

后一项是local[i-1][j] + diff是指在i-1天就进行了最多j次交易，i天进行最后一次交易，原本是i-1天卖的现在变成i天卖。

然后是更新全局变量:

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

比较前一天的全局最优和当天的局部最优，取大的那一个。

Method 2用了降维方法节省空间。

但是注意双重loop 的内层loop, j是从k向小变到1, 因为一维空间只能保存当前一行内容，更新local时用到了了global[i-1][j-1].

若是从前往后走到了i, j时，[i-1][j-1]会被[i][j-1]覆盖掉，所以要从后往前走。

Method 1 Time Complexity: O(prices.length * k), k是最多交易次数，这里k=2. Space: O(prices.length*k).

Method 2 Time Complexity: O(prices.length * k). Space: O(k).

AC Java:

1 public class Solution { 2     public int maxProfit(int[] prices) { 3         return helper(prices,2); 4     } 5     private int helper(int[] prices, int k){ 6         if(prices == null || prices.length == 0){ 7             return 0; 8         } 9         /*10         //Method 111         int[][] local = new int[prices.length][k+1];12         int[][] global = new int[prices.length][k+1];13         for(int i = 1; i
     
      =1; j--){29                 local[j] = Math.max(global[j-1] + Math.max(diff,0), local[j]+diff);30                 global[j] = Math.max(global[j], local[j]);31             }32         }33         return global[k];34     }35 }