?LeetCode刷題實(shí)戰(zhàn)188：買(mǎi)賣(mài)股票的最佳時(shí)機(jī) IV

示例 1：

輸入：k = 2, prices = [2,4,1]
輸出：2
解釋?zhuān)涸诘?1 天 (股票價(jià)格 = 2) 的時(shí)候買(mǎi)入，在第 2 天 (股票價(jià)格 = 4) 的時(shí)候賣(mài)出，這筆交易所能獲得利潤(rùn) = 4-2 = 2 。

示例 2：

輸入：k = 2, prices = [3,2,6,5,0,3]
輸出：7
解釋?zhuān)涸诘?2 天 (股票價(jià)格 = 2) 的時(shí)候買(mǎi)入，在第 3 天 (股票價(jià)格 = 6) 的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 6-2 = 4 。
隨后，在第 5 天 (股票價(jià)格 = 0) 的時(shí)候買(mǎi)入，在第 6 天 (股票價(jià)格 = 3) 的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 3-0 = 3 。
?

提示：

0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

class?Solution?{ 
????public?int?quick(int[] prices){
????????int?max=0;
????????for(int?i=0;i-1;i++){
????????????if(prices[i+1]>prices[i])
????????????max+=(prices[i+1]-prices[i]);
????????}
????????return?max;
????}
????
????public?int?maxProfit(int?k, int[] prices) {
????????int?len=prices.length;
???????
??????if(len==1||len==0||prices==null||k==0){
??????????return?0;
??????}
??????if(k>=len/2){
????????return?quick(prices);
??????} 
????????int?[]buy=new?int[k+1];
????????int?[]sell=new?int[k+1];
????????for(int?i=0;i<=k;i++){
????????????buy[i]=Integer.MIN_VALUE;
????????}
????????for(int?i=0;i????????????for?(int?j = 0; j????????????????buy[j+1] = Math.max(buy[j+1], sell[j] - prices[i]);
????????????????sell[j+1] = Math.max(buy[j+1] + prices[i], sell[j+1]);
????????????}
????????????
????????}
????????return?sell[k];
????????
????}
}