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

采用動态規劃來解決問題。

我們需要維護如下兩個量：

<code>global[i][j]</code>:目前到達第<code>i</code>天最多可以進行<code>j</code>次交易，所得到的最大利潤。

<code>local[i][j]</code>:目前到達第<code>i</code>天最多可以進行<code>j</code>次交易，而且最後一次交易在當天賣出，所得到的最大利潤。

狀态轉移方程：

<code>global[i][j] = max(local[i][j], global[i-1][j])</code>

上述方程比較兩個量的大小：①目前局部最大值；②過往全局最大值。

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

上述方程比較兩個量的大小：

①全局到<code>i-1</code>天進行<code>j-1</code>次交易，然後加上今天的交易（如果今天的交易賺錢的話）。

②取局部第<code>i-1</code>天進行<code>j</code>次交易，然後加上今天的內插補點（<code>local[i-1][j]</code>是第<code>i-1</code>天賣出的交易，它加上<code>diff</code>後變成第<code>i</code>天賣出，并不會增加交易次數。無論<code>diff</code>是正還是負都要加上，否則就不滿足<code>local[i][j]</code>必須在最後一天賣出的條件了）

另外需要注意的一個問題是，當k遠大于數組的大小時，上述算法将變得低效。是以将其改用不限交易次數的方式解決。