题目链接
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吧，可以参考如下解释：
