AcWing 895. 最长上升子序列
原题链接
简单
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int nn=1010;
int a[nn];
int f[nn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<n;j++)
{
if(a[i]>a[j])
{
f[i]=max(f[i],f[j]+1);
}
}
}
int ans=1;
for(int i=1;i<=n;i++)
{
ans=max(ans,f[i]);
}
cout<<ans<<endl;
return 0;
}
//再附上一篇打印路径的代码。
主要使用pre数组存储,用递归函数从尾部到头部打印
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int nn=205;
int a[nn];
int f[nn];
int pre[nn];
int pos;
void print(int x)
{
if(x==0)
return ;
print(pre[x]);
if(pre[x])cout<<" ";
cout<<a[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
{
if(a[j]<=a[i])
{
if(f[j]+1>f[i])
{
f[i]=f[j]+1;
pre[i]=j;
}
}
}
}
int ans=1;
for(int i=1;i<=n;i++)
{
if(ans<f[i])
{
ans=f[i];
pos=i;
}
}
cout<<ans<<endl;
print(pos);
return 0;
}