题目链接

Best Time to Buy and Sell Stock IV

Say you have an array for which the ith
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.
Note:You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

解答思路

TODO （稍后补充）

解题代码

class Solution {
public:
    int getMaxProfileWhenKGtLen(vector<int>& prices) {
        int maxProfit = 0;
        for (int i=1;i<prices.size();i++) {
            maxProfit = (prices[i]-prices[i-1])>=0 ? (maxProfit+prices[i]-prices[i-1]) : maxProfit;
        }
        return maxProfit;
    }
    int maxProfit(int k, vector<int>& prices) {
        
        if (prices.empty()) return 0;
        if (k >= prices.size()) return getMaxProfileWhenKGtLen(prices);
        
        /*
        // generate maxKProfit[prices.size()][k] and curKProfit[prices.size()][k]
        int **maxKProfit = new int*[prices.size()];
        int **curKProfit = new int*[prices.size()];
        for (int i=0;i<prices.size();i++) {
            maxKProfit[i] = new int[k+1];
            curKProfit[i] = new int[k+1];
        }
        
        maxKProfit[0][0] = 0;
        curKProfit[0][0] = 0;
        maxKProfit[0][1] = 0;
        curKProfit[0][1] = 0;*/
        
        vector<vector<int> > maxKProfit(prices.size(), vector<int>(k+1, 0));
        vector<vector<int> > curKProfit(prices.size(), vector<int>(k+1, 0));
        
        for (int i=1;i<prices.size();i++) {
            for (int w=1;w<=k && w<=i;w++) {
                int diffI = prices[i] - prices[i-1];
                int tmpMax = maxKProfit[i-1][w-1] >= maxKProfit[i-1][w-1]+diffI ? maxKProfit[i-1][w-1] : maxKProfit[i-1][w-1]+diffI;
                tmpMax = tmpMax >= curKProfit[i-1][w]+diffI ? tmpMax : curKProfit[i-1][w]+diffI;
                curKProfit[i][w] = tmpMax;
                maxKProfit[i][w] = maxKProfit[i-1][w] >= curKProfit[i][w] ? maxKProfit[i-1][w] : curKProfit[i][w];
            }
        }
        return maxKProfit[prices.size()-1][k];
        
    }
};

遇到Test Cases和Submission的结果不同的问题

如果用c++指针，会引起一些不确定性行为，所以尽量用vector吧，可以参考如下解释：

不确定性的解释