主要是状态的设计和状态的转移

设计：增加2维： 结束时有无股票，有无买卖

转移：如下所示

代码（抄袭者死）

#include<bits/stdc++.h>
using namespace std;
int n;
int ans;
int m[10005],q[10005][2][2];//-->天数 结束时有无股票 有无买卖
int main()
{
    cin>>n;
    if(n==1)
    {
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++)cin>>m[i];
    q[1][1][1]=-m[1];
    q[1][1][0]=-INT_MAX;
    for(int i=2;i<=n;i++)
    {
        q[i][0][0]=max(q[i-1][0][0],q[i-1][0][1]);
        q[i][0][1]=max(q[i-1][1][0],q[i-1][1][1])+m[i];//卖出
        q[i][1][0]=max(q[i-1][1][0],q[i-1][1][1]);
        q[i][1][1]=q[i-1][0][0]-m[i];//买入
    }
    for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)
    {
        ans=max(ans,q[n][i][j]);
    }
    cout<<ans;
    return 0;
}

求点赞😄

这个问题可以使用动态规划来解决。我们需要维护两个状态数组，buy和sell，分别表示持有股票和不持有股票时的最大利润。

对于第i天来说，我们有两种选择：

1. 如果在第i天买入股票，那么我们的利润就是在第i-2天结束时的最大利润减去第i天的股票价格。也就是buy[i] = sell[i-2] - prices[i]。
2. 如果在第i天不买入股票，那么我们的利润就是在第i-1天结束时的最大利润。也就是buy[i] = buy[i-1]。

对于卖出股票的情况，我们也有两种选择：

1. 如果在第i天卖出股票，那么我们的利润就是在第i-1天结束时的最大利润加上第i天的股票价格。也就是sell[i] = buy[i-1] + prices[i]。
2. 如果在第i天不卖出股票，那么我们的利润就是在第i-1天结束时的最大利润。也就是sell[i] = sell[i-1]。

最后，我们的答案就是在第n天结束时，不持有股票的最大利润。也就是max(sell[n], buy[n])。

使用动态规划的思路，我们可以从左到右遍历数组，依次计算出每一天结束时的最大利润。时间复杂度为O(n)。

希望这个解析能够帮助你理解问题并实现代码。如果有任何疑问，请随时提出。

#include <iostream>
#include <vector>

using namespace std;

int maxProfit(int n, vector<int>& prices) {
    if (n <= 1) {
        return 0;
    }

    vector<int> buy(n + 1, 0);
    vector<int> sell(n + 1, 0);

    buy[1] = -prices[0];

    for (int i = 2; i <= n; i++) {
        buy[i] = max(sell[i-2] - prices[i-1], buy[i-1]);
        sell[i] = max(buy[i-1] + prices[i-1], sell[i-1]);
    }

    return max(sell[n], buy[n]);
}

int main() {
    int n;
    cin >> n;

    vector<int> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }

    cout << maxProfit(n, prices) << endl;

    return 0;
}

到第i天的时候有三种状态： 已买入：第 i-1天就已经持有股票，或者第i-1天是可买入状态并在第i天买入了股票。 可买入（非冷冻期）：第i-1天就已经是可买入状态，或者第i-1天是冷冻期。 冷冻期：第i-1天是已买入状态并在第i天出售了股票。 我们可以这样表示三种状态 f[i][0]：表示在第i天结束之后，处于[已买入]状态，此时的最大利润

f[i][1]：表示在第i天结束之后，处于[可买入]状态，此时的最大利润

f[i][2]：表示在第i天结束之后，处于[冷冻期]状态，此时的最大利润

根据上面的分析可以得到状态转移方程： f[i][0] = max(f[i - 1][0], f[i - 1][1] - a[i]); f[i][1] = max(f[i - 1][2], f[i - 1][1]); f[i][2] = f[i-1][0] + a[i]; 买入股票时需要用利润减去股票当前价格a[i],售出股票时利润增加股票当前价格a[i]。

//最初利润为0，若第一天是买入状态，利润为-a[1],若第一天是可买入状态，说明第一题没有买股票，利润为0，第一天不可能为冷冻期。
    f[1][0] = -a[1];
	for(int i = 2; i <= n; i++)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][1] - a[i]);
        f[i][1] = max(f[i - 1][2], f[i - 1][1]);
        f[i][2] = f[i-1][0] + a[i];
    }