188 Best Time to Buy and Sell Stock IV——leetcode

 

class Solution {
public:
    Solution(){}

    int maxProfit(int K, vector<int> &prices) {
        vector<int> lowVec;
        vector<int > highVec;

        if(prices.size() <=1){
            return 0;
        }
        prices.erase(std::unique(prices.begin(),prices.end()),prices.end());
        if(prices.size() <=1){
            return 0;
        }
        lowVec.reserve(prices.size()/2);
        highVec.reserve(prices.size()/2);

        if(prices[0]<prices[1]){
            lowVec.push_back(prices[0]);
        }

        for(int i=1;i<prices.size()-1;i++){
            int low;
            int cur = prices[i];
            if(cur<prices[i+1] && cur<prices[i-1]){
                lowVec.push_back(cur);
            }
            if(cur>prices[i-1]&&cur>prices[i+1]){
                highVec.push_back(cur);
            }
        }
        if(prices[prices.size()-2]<prices[prices.size()-1]){
            highVec.push_back(prices.back());
        }


        int N = lowVec.size();
        if(K>=N){
            int sum=0;
            for(int i=0;i<N;i++){
                sum += highVec[i]-lowVec[i];
            }
            return sum;
        }
        
        vector<vector<int> > opt ;
        opt.resize(K+1);
        for(int i=0;i<K+1;i++)
        {
            opt[i].resize(N);
        }

        vector<int>diff;
        diff.reserve(lowVec.size());
        int sum=0;
        for(int i=0;i<N;i++){
            sum += (highVec[i]-lowVec[i]);
            diff.push_back(sum);
        }
        
        for(int k=1;k<=K;k++)
        {
            for(int i=0;i<k;i++){
                opt[k][i]= diff[i];
            }
        }
        for(int i=0;i<N;i++){
            opt[0][i]=0;
        }
       
        for(int k=1;k<=K;k++)
        {
            for(int i=k;i<N;i++)
            {
                opt[k][i] = max(opt[k][i-1],opt[k-1][i-1]+highVec[i]-lowVec[i]);
                opt[k][i] = max(opt[k][i],highVec[i]-lowVec[0]);
                for(int t=i-1;t>=k-1 && t>0;t--){
                    int highDiff = highVec[i]-highVec[t];
                    int lowDiff = lowVec[i]-lowVec[t];
                    if(highDiff>0 && lowDiff>0){
                        opt[k][i]=max(opt[k][i],opt[k-1][t-1]+highVec[i]-lowVec[t]) ;    
                    }
                    else break;
                }
            }
        }
        return opt[K][N-1];
   }
};

 

 

188	Best Time to Buy and Sell Stock IV

说明：有个地方不同其他程序。即先删除一些无用的状态(即非波峰波谷，这些状态属于中间态，因此，肯定赚钱不了的），比如 {2,3,4,3,2}其中的3就是无用状态。对于最后一个元素，如果不是涨价，也是无用，第一个元素，如果不比第二个元素小，也是无效状态

 

动态规划的主要公式：

opt[k][i]=max(opt[k][i],opt[k-1][t-1]+highVec[i]-lowVec[t]) 

即，如果选择当前第i个股价卖出，那么，需要选取第t个股价买入（0<=t<i),同时在t前面选择k-1个操作即opt[k-1][t-1]