AcWing 1058. 股票买卖 V---空间优化单数组f[3],20行代码。
原题链接
中等
作者:
若根
,
2022-07-08 12:20:56
,
所有人可见
,
阅读 105
算法1
y总写法 无优化
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int f[120000][3];
int main(void)
{
int n;
scanf("%d",&n);
for(int i=0;n>=i;i++)
{
f[i][1]=-0x3f3f3f3f;
}
for(int i=1;n>=i;i++)
{
int a;
scanf("%d",&a);
f[i][0]=max(f[i-1][0],f[i-1][2]);//我们发现都是用的i-1,也就是上一层的代码,所以可以优化
f[i][1]=max(f[i-1][1],f[i-1][0]-a);
f[i][2]=f[i-1][1]+a;//与y总不同,我将0表示没有货且可买,1表示有货,2表示才卖。
}
int ans=0;
for(int i=1;n>=i;i++)
{
ans=max(ans,max(f[i][0],f[i][2]));
}
cout<<ans;
return 0;
}
算法2
优化空间
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int f[3];
int main(void)
{
int n;
scanf("%d" ,&n);
f[1]=-0x3f3f3f3f;
for(int i=1;n>=i;i++)
{
int a;
scanf("%d",&a);
int t=f[0];
f[0]=max(f[0],f[2]);
f[2]=f[1]+a;//完全省去前一维,但要调整一下位置,又由于他们循环使用到了,所以需要一个t存储一下。
f[1]=max(f[1],t-a);//与y总不同,我将0表示没有货且可买,1表示有货,2表示才卖。
}
cout<<max(f[0],f[2]);
return 0;
}