[LeetCode] Best Time to Buy and Sell Stock IV 買賣股票的最佳時間之四

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

Credits:

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

其中局部最優值是比較前一天并少交易一次的全局最優加上大于0的內插補點，和前一天的局部最優加上內插補點後相比，兩者之中取較大值，而全局最優比較局部最優和前一天的全局最優。