最长不上升子序列
陈子骏
2018-04-02 17:45:17
```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[500001],d[500001],f[500001];
int ans=1,t,cnt;
//用d[i]维护f值为i的最后一个导弹的位置，t记录当前已经求出最长不升子序列长度
//用f[i]储存以i结尾的最长不上升子序列长度
int main()
{
while(~scanf("%d",&a[++cnt]));
cnt--;
for(int i=1;i<=cnt;i++)
{
f[i]=1;
for(int j=t;j>0;j--)
if(a[i]<=a[d[j]])
{
f[i]=f[d[j]]+1;
break;
}
t=max(t,f[i]);
d[f[i]]=i;
ans=max(ans,f[i]);
}
printf("%d\n",ans);
ans=1;t=0;
for(int i=1;i<=cnt;i++)
{
f[i]=1;
for(int j=t;j>0;j--)
if(a[i]>a[d[j]])
{
f[i]=f[d[j]]+1;
break;
}
t=max(t,f[i]);
d[f[i]]=i;
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}
```