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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int k;
    scanf("%d", &k);
    vector<int> prices(k);
    int a;
    for(int i = 0; i < k; ++i)
    {
        scanf("%d", &a);
        prices[i] = a;
    }
    int max_num = 2;
    vector<vector<vector<int>>> dp(k, vector<vector<int>>(max_num + 1, vector<int>(2)));  //使用动态规划数组dp，该数组代表第i天，最大允许交易次数为j次时，未持股（第三维为0）或持股（第三维为1）时利润最大值
    for(int i = 0; i < k; ++i)   //初始值，当允许交易次数为0时的初始化
    {
        dp[i][0][0] = 0;    //不允许交易且不持股，最大利润为0
        dp[i][0][1] = -prices[i];   //不允许交易且持股，只能亏钱
    }
    for(int i = 1; i <= max_num; ++i)  //初始值，对第一天各种情况的初始化
    {
        dp[0][i][0] = 0;
        dp[0][i][1] = -prices[0];
    }
    for(int i = 1; i < k; ++i)
    {
        for(int j = 1; j <= max_num; ++j)
        {
            dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
            dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);  //每次买入为交易的开始
        }
    }
    if(dp[k - 1][max_num][0] > 0)
    printf("%d", dp[k - 1][max_num][0]);
    else
    printf ("%d", 0);
    return 0;
}
// 64 位输出请用 printf("%llcstdiod")