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が無駄な状態である.最後の要素については、値上げでなければ役に立たず、最初の要素は、2番目の要素より小さくなければ無効な状態です.
 
動的計画の主な式:

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

すなわち、現在i番目の株価売りを選択すると、t番目の株価買い(0<=t