###### tags: `LeetCode` `Dynamic Programming` `Hard`
# LeetCode #188 [Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv)
### (Hard)
給定一個整數數組 prices ，它的第 i 個元素 prices[i] 是一支給定的股票在第 i 天的價格。
設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

---
動態規劃題
令sold[k]為第k次賣出後的狀態, hold[k]為第k次買入後的狀態. 可得關係:
hold[k]=sold[k-1]-prices[i] (完成第k-1次賣出後又買入)
sold[k]=hold[k]+prices[i] (完成第k次買入後賣出)

一開始先判斷k的大小, 若k≥prices.size()/2的話, 則可以自由買賣不必考慮次數限制, 與Best Time To Buy and Sell Stock II相同。反之則遍歷prices[i], 每次都考慮k筆交易並得到最大收益sold[k]。遍歷完prices[i]後的最大收益即為sold[k]。

---

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size()>=2){
            if(k>prices.size()/2){
                int ans=0;
                for(int i=0;i<prices.size()-1;i++){
                    ans+=max(prices[i+1]-prices[i],0);
                }
                return ans;
            }
            int hold[k+1];
            int sold[k+1];
            for(int i=0;i<=k;i++){
                hold[i]=INT_MIN;
                sold[i]=0;
            }
            for(int i=0;i<prices.size();i++){
                for(int j=1;j<=k;j++){
                    hold[j]=max(hold[j], sold[j-1]-prices[i]);
                    sold[j]=max(hold[j]+prices[i], sold[j]);
                }
            }
            return sold[k];
        }
        return 0;
    }
};