188. Best Time to Buy and Sell Stock IV

Solution

class Solution {
public:
    int maxProfit(int k, vector<int>& prices)
    {
        if (prices.empty()) return 0;
        if (k >= prices.size()) return getMaxProfit(prices);
        
        vector<int> curMaxProfit(k + 1);
        vector<int> maxProfit(k + 1);

        // 到達第 i 天的時候，最多可以進行 j 次交易
        for (int i = 1; i < prices.size(); ++i)
        {
            int diff = prices[i] - prices[i - 1];
            for (int j = k; j >= 1; --j)
            {
                curMaxProfit[j] = max(maxProfit[j - 1] + max(diff, 0), curMaxProfit[j] + diff);
                maxProfit[j] = max(maxProfit[j], curMaxProfit[j]);
            }
        }
        return maxProfit[k];        
    }

    int getMaxProfit(vector<int> &prices)
    {
        int maxProfit = 0;
        for (int i = 1; i < prices.size(); ++i)
        {
            if (prices[i] > prices[i - 1])
            {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }    
};

• 時間複雜度：
  $O(n\cdot k)$
• 空間複雜度：
  $O(n\cdot k)$