这题可能还比上一题简单些。
考虑到冷冻期的加入,我们附加”冷冻期”这个状态,即在f[0/1][i]表示只考虑前i支股票,当前没有/有股票的最大收益
的基础上,再设f[2][i]表示只考虑前i支股票,且处于冷冻期的最大收益
那么转移略作修改,令f[1][i]
转移至f[2][i],f[2][i]
再转移至f[0][i]
即可。
时间复杂度$O(n)$
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
#define MAXN 200011
ll f[3][MAXN];
int main()
{
ll n,x;
scanf("%lld",&n);
memset(f,0xcf,sizeof f);
f[0][0]=0;
for(ll i=1;i<=n;++i)
{
scanf("%lld",&x);
f[0][i]=std::max(f[0][i-1],f[2][i-1]);
f[1][i]=std::max(f[1][i-1],f[0][i-1]-x);
f[2][i]=std::max(f[2][i-1],f[1][i-1]+x);
}
printf("%lld",std::max(f[0][n],std::max(f[1][n],f[2][n])));
return 0;
}