188 Best Time to Buy and Sell Stock IV

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.

Solution

class Solution {
public:
    int maxProfit2(vector<int>& prices ) {
        int res = 0, n = prices.size();
        for ( int i = 1; i <= n-1; i++ ) {
            if ( prices[i] > prices[i-1] ) res += prices[i] - prices[i-1];
        }
        return res;
    }
    int maxProfit(int k, vector<int>& prices) {
        if ( k == 0 ) return 0;
        int n = prices.size();
        if ( n == 0 ) return 0;
        if ( k >= n/2 ) return maxProfit2(prices);
        vector<int> result_do(k, 0), result_dont(k, 0), tmp_do(k, 0), tmp_dont(k, 0);
        int maxP = 0;
        for ( int i = 1; i <= n-1; i++ ) {
            // don't - j: don't - j vs. do - j
            for ( int j = 0; j <= k-1; j++ ) tmp_dont[j] = max(result_do[j], result_dont[j]);
            // do - 1
            tmp_do[0] = max(0, result_do[0]) + prices[i] - prices[i-1];
            maxP = max(maxP, tmp_do[0]);
            // do - j (tmp[k-1+j])
            for ( int j = 1; j <= k-1; j++ ) {
                tmp_do[j] = max(result_dont[j-1], result_do[j]) + prices[i] - prices[i-1];
                maxP = max(maxP, tmp_do[j]);
            }
            result_do.swap(tmp_do);
            result_dont.swap(tmp_dont);
        }
        return maxP;
    }
};