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

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

int main() {
    int n,k;
    cin>>n>>k;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<vector<int>> dp(k,vector(2,0));
    //对买入的股票花销赋初值
    for(int i=0;i<k;i++){
        dp[i][0]=-arr[0];
    }
    //遍历
    for(int i=1;i<n;i++){
        //i时刻第一次买入
        dp[0][0]=max(dp[0][0],-arr[i]);
        //i时刻第一次卖出
        dp[0][1]=max(dp[0][1],dp[0][0]+arr[i]);
        for(int j=1;j<k;j++){
            //i时刻第j+1次买入
            dp[j][0]=max(dp[j][0],dp[j-1][1]-arr[i]);
            //i时刻第j+1次卖出,收益为i-1时刻卖出与i时刻卖出的收益最大值
            dp[j][1]=max(dp[j][1],dp[j][0]+arr[i]);
        }
    }
    cout<<dp[k-1][1];
    return 0;
}
// 64 位输出请用 printf("%lld")