题解 | #买卖股票的最好时机(四)#

#include <climits>
#include <vector>
#include <iostream>
#include <ostream>
using namespace std;

int main() {
    int n, t,i,j,k,cur,prev,max_deal;
    cin >>n>>max_deal;
    max_deal=min(n/2,max_deal);
    vector<vector<vector<int>>> dp(2,vector<vector<int>>(max_deal+1,vector<int>(2,0)));
    //dp[i][j][k]代表第i天，最多已买入次数（含今次），今天结束时是否持股,存储此时的账户最大余额
    cin>>t;
    
    for(i=0;i<2;++i){
        for(j=1;j<=max_deal;++j){
            dp[i][j][1]=-t;
        }
    }
    //cout<<n<<' '<<max_deal<<" "<<t<<endl;
    for(i=1;i<n;++i){
        cin>>t;
        cur=i%2;
        prev=(i-1)%2;
        for(j=1;j<=max_deal;++j){
            dp[cur][j][0]=max(dp[prev][j][0],dp[prev][j][1]+t);//保持空仓，或卖出手中
            dp[cur][j][1]=max(dp[prev][j][1],dp[prev][j-1][0]-t);//买入，或保持持仓。如果总交易只有1则不考虑上次交易
            //cout<<i<<' '<<j<<' '<<dp[cur][j][0]<<' '<<dp[cur][j][1]<<"|";
        }  
      //cout<<endl;
    }
    cout<<dp[cur][max_deal][0]<<endl;
    }