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

#include <iostream>  // 包含输入输出流库
#include<algorithm>  // 包含算法库（如 max 函数）
using namespace std;

int main() {
    int dp[100005][5] = {0};  // 定义一个动态规划数组 dp，并初始化为 0
    int n, price[100005];  // 定义变量 n 和价格数组 price
    cin >> n;  // 输入天数 n
    for(int i = 1; i <= n; i++) {
        cin >> price[i];  // 输入每一天的价格
    }
    
    // 初始化第 1 天的状态
    dp[1][1] = -price[1];  // 第 1 天买入股票的状态，花费为 -price[1]
    dp[1][3] = -price[1];  // 第 1 天进行第二次买入的状态，也为 -price[1]
    
    // 从第 2 天开始迭代计算
    for(int i = 2; i <= n; i++) {
        dp[i][0] = dp[i-1][0];  // 第 i 天没有操作，状态与前一天相同
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i]);  // 第 i 天第一次买入，或保持不变
        dp[i][2] = max(dp[i-1][2], dp[i-1][1] + price[i]);  // 第 i 天第一次卖出，或保持不变
        dp[i][3] = max(dp[i-1][3], dp[i-1][2] - price[i]);  // 第 i 天第二次买入，或保持不变
        dp[i][4] = max(dp[i-1][4], dp[i-1][3] + price[i]);  // 第 i 天第二次卖出，或保持不变
    }
    
    // 输出最大利润（比较 dp[n][4] 和 dp[n][0]，即卖出两次后的最大值与不操作的最大值）
    cout << max(dp[n][4], dp[n][0]) << endl;
}