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

只能交易两次，还是从状态出发
dp[i][0]：第i天第一次持有
dp[i][1]: 第i天第一次未持有/卖出 dp[i][2]：第i天第二次持有
dp[i][3]：第i天第二次未持有/卖出
状态转移：
dp[i][0] = max(dp[i-1][0]"维持状态，和前一天一样处于第一次持有状态，收益不变", -p[i]"第一次买入，总收益为-p[i]，花掉了当前价格的钱")
dp[i][1] = max(dp[i-1][1]"维持状态，未持有，没买过",dp[i-1][0]+p[i]"前一天还持有，今天卖了，收益就是加上今天价格")
dp[i][2] = max(dp[i-1][2]"维持状态，还是和前一天一样，继续第二次的持有", dp[i-1][1]-p[i]"状态变化：前一天是第一次卖出，今天买了，收益变成dp[i-1][1]-p[i]")
dp[i][3] = max(dp[i-1][3]"维持状态，还是和前一天一样，处于一种未持有的状态，就是已经卖过了", dp[i-1][2]+p[i]"状态变化，前一天还第二次持有，今天卖了，收益增加")

#include <cstdio>
#include <iostream>
using namespace std;
const int N  = 1e5+10;
int p[N];
int dp[N][4];
int n;
int main() {
    scanf("%d", &n);
    for(int i = 1;i<=n;i++){
        scanf("%d", &p[i]);
    }
    dp[1][0] = 0-p[1];
    dp[1][1] = 0;
    dp[1][2] = 0-p[1];
    dp[1][3] = 0;
    for(int i = 2;i<=n;i++){
        dp[i][0] = max(dp[i-1][0], -p[i]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + p[i]);
        dp[i][2] = max(dp[i-1][2], dp[i-1][1]-p[i]);
        dp[i][3] = max(dp[i-1][3], dp[i-1][2]+p[i]);

    }
    printf("%d", max(max(dp[n][0], dp[n][1]), max(dp[n][2], dp[n][3])));
    return 0;
}