参考资料 http://www.cnblogs.com/grandyang/p/4281975.html

先摆公式

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])

比较容易的理解方式

名词

global[i][j] 到第 i 天为止，交易 j 次的最大收益。
local[i][j] 到 i 天为止，交易 j 次，且第 j 次卖出发生在第 i 天。

推导

买入操作不影响收益，只需考虑卖出操作。

求 global[i][j] , 有几种情况

1. 第 i 天有卖出：local[i][j]
2. 第 i 天没有卖出，继承第 i-1 天的值：global[i-1][j]
   global[i][j] = max( local[i][j], global[i-1][j] )

求 local[i][j]，有几下几种情况，这时约束条件是第 i 天有卖出，所以需要对哪天买入进行区分：

1. 第 i-1 天买入，第 i 天卖出：global[i-1][j-1] + (prices[i] - prices[i-1])
2. 在第 i-1 天前的某天买入，第 i 天卖出：local[i-1][j] + (prices[i] - prices[i-1])
   这个推导可以理解为 在第 i-1 卖出的基础上进行修正，第 i-1 天卖，改成第 i 天卖，所以加上差值 prices[i] - prices[j]
3. 1 所说的情况，只有在 prices[i] > prices[i-1] 时才应采纳，否则不应该在第 i 天卖出，而 local 约束必须在第 i 天卖出，那么我们就说在第 i 天买，然后第 i 天卖出，结果是 global[i-1][j-1] + 0
   local[i][j] = max( global[i-1][j-1] + (prices[i] - prices[i-1]), local[i-1][j] + (prices[i] - prices[i-1]), global[i-1][j-1] + 0)

以上解法，空间占用为 2 * sizeof(int) * prices.length() * k，在提交过程中有一个case k非常大，内存会爆。这种时候，看了一下 prices 都比较小，prices.length() < k，这时相当于不先买卖次数求最大收益，使用 Best Time to Buy and Sell Stock II 的解法即可轻松搞定。