188. Best Time to Buy and Sell Stock IV

class Solution {
public:
    int maxProfit(int k, vector<int>& prices)
    {
        int n = prices.size();

        if (n == 0) return 0;

        if (k >= n) return getMaxProfit(prices);

        vector<int> curMaxProfit(k + 1, 0);
        vector<int> maxProfit(k + 1, 0);

        for (int i = 1; i < n; i++)
        {
            int diff = prices[i] - prices[i - 1];
            for (int j = k; j >= 1; j--)
            {
                curMaxProfit[j] = max(curMaxProfit[j] + diff, maxProfit[j - 1] + max(0, 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;
    }
};

• T: $O(N \cdot K)$
• S: $O(N \cdot K)$