居然没有题解。。那我来写
前置题目【大盗阿福】中已经提到,用f[0/1][i]
表示两种状态,这题也是类似的。
设f[0][i]表示考虑前i支股票,且手头没有股票的最大收益;
f[1][i]表示考虑前i支股票且手头有股票(由题意,手头最多一只股票)的最大收益
因为每一天要么买/卖,要么什么也不干,故可得转移:
$$f[0][i]=max(f[0][i-1],f[1][i-1]+a[i])$$
$$f[1][i]=max(f[1][i-1],f[0][i-1]-a[i])$$
注意到f[1][i]可能是负数,要先初始化成负无穷
时空$O(n)$
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
#define MAXN 200011
ll f[2][MAXN];
int main()
{
memset(f,0xcf,sizeof f);
ll n;
scanf("%lld",&n);
f[0][0]=0;
for(ll i=1;i<=n;++i)
{
ll x;
scanf("%lld",&x);
f[1][i]=std::max(f[1][i-1],f[0][i-1]-x);
f[0][i]=std::max(f[0][i-1],f[1][i-1]+x);
}
printf("%lld",std::max(f[0][n],f[1][n]));
return 0;
}
您好,我想问一下, memset(f,0xcf,sizeof f); 为什么要将 f 数组中的元素设定为无穷小,为什么设定为 -1 或 0 (非正数) 就不对呢?
因为买入股票的时候,手中的钱可能是负数