188. Best Time to Buy and Sell Stock IV

problem description

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.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

algorithm thought

这是这系列的第四题，第一题是只能一次交易，第二题是可以任意次交易，第三题是可以两次交易，这三题都能O(n)时间内完成。这题是可以k次交易，其实在第三题（可以完成两次交易）已经可以从两次交易推出任意次交易的情况了。只是每次遍历到一个商品，就要进行k次交易，时间复杂度太高了，一共211个test cases在209个的时候TEL了。这种方法也会把代码贴出来

其实上面这个方法是可行的，但是还需要考虑优化。如果一共只有n个价格，那么最多就进行n/2次交易。换句话说，如果k>n/2，那么就可以认为可以进行任意次交易。将时间复杂度降到O(n).如果不这么处理的话，时间复杂度降是O(kn)，空间复杂度也会达到O(k)。所以加一个短处理对时间复杂度影响挺大的

code

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        k=min(k,int(prices.size()));
        vector<pair<int,int>> tc(k+1,make_pair(INT_MIN,0));
        for(auto p:prices){
            for(int i=1;i<=k;++i){
                tc[i].first=max(tc[i].first,tc[i-1].second-p);
                tc[i].second=max(tc[i].second,tc[i].first+p);
            }
        }
        return tc.back().second;
    }
};


//加了快速处理
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(k>prices.size()/2){
            return shortPro(prices);
        }
        vector<pair<int,int>> tc(k+1,make_pair(INT_MIN,0));
        for(auto p:prices){
            for(int i=1;i<=k;++i){
                tc[i].first=max(tc[i].first,tc[i-1].second-p);
                tc[i].second=max(tc[i].second,tc[i].first+p);
            }
        }
        return tc.back().second;
    }
    int shortPro(vector<int>&prices){
        int res=0;
        for(int i=1;i<prices.size();++i){
            if(prices[i]>prices[i-1]){
                res+=(prices[i]-prices[i-1]);
            }
        }
        return res;
    }
};

algorithm analysis

对于第一个算法，时间复杂度是O(kn)。对于第二个加了快速处理的方法，在LeetCode上运行时间能降到4ms，复杂度分析应该要用均摊分析。也不太了解，就不多分析了。