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

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


int main(){
    int n;cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    vector<vector<int>> dp(n,vector(5,0));
    //初始化：
    dp[0][1]=-arr[0];
    dp[0][3]=-arr[0];
    for(int i=1;i<n;i++){
        dp[i][0]=dp[i-1][0];//不进行任何操作
//获取第一次买入最少的花销，该花销为上一时刻买入和当前时刻买入的最大值
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]-arr[i]);
//获取第一次卖出最大的收益，该收益为上一时刻卖出和当前时刻卖出的最大值
        dp[i][2]=max(dp[i-1][2],dp[i-1][1]+arr[i]);
//获取第二次买入最少的花销，该花销为上一时刻买入和当前时刻买入的最大值
        dp[i][3]=max(dp[i-1][3],dp[i-1][2]-arr[i]);
//获取第二次卖出最大的收益，该收益为上一时刻卖出和当前时刻卖出的最大值
        dp[i][4]=max(dp[i-1][4],dp[i-1][3]+arr[i]);
    }
    cout<<dp[n-1][4];
    return 0;
}
// 64 位输出请用 printf("%lld")