[060] LeetCode 188演算法【Best Time to Buy and Sell Stock IV】 股票機器人 IV

188. Best Time to Buy and Sell Stock IV (Hard)

Say you have an array for which the i-th 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).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

這題跟上一題的思路是一模一樣，而且你最多可以完成k筆交易，我們只要把我們之前的動態規劃模板拿過來使用就可以了。

這題有個比較特別的地方，假設K>input.length/ 2，就表示可交易無限次，因為每一次交易都有買跟賣兩個動作，那直接取最大利潤就可以了。

這次我們用下面參數去測試我們的代碼：

Input: [1,2,4,1,8,9,10,2,9], k = 2
dptable: 
[0, 0, 0, 0, 0,  0,  0,  0,  0], 
[0, 1, 3, 3, 7,  8,  9,  9,  9], 
[0, 1, 3, 3, 10, 11, 12, 12, 16]

所謂的動態規劃就是把遞迴精簡化，利用DPtable來紀錄已經算過的部分，不用多算進而達到優化。

大家加油。

上一篇：[059] LeetCode 123演算法【Best Time to Buy and Sell Stock III】 股票機器人 III

下一篇：[061] LeetCode 309演算法【Best Time to Buy and Sell Stock with Cooldown】 股票機器人擬人版