最长上升子序列
题目 最长上升子序列
思路分析
3 1 2 1 8 5 6中找到的最长上升子序列是 1 2 5 6 长度为4
可以用f[i]表示以a[i]结尾的上升子序列最大长度
有点类似于kmp算法 对于f[i]只需要找到它前面的比它小的一个数的f[j] 然后在它的基础上加1即可推到当前的f[i]
比如：f[7]表示以a[7]也就是6结尾的最长上升子序列的长度 那么它的状态就是从前面的 12 125……转移过来 长度就是2+1或3+1中更大的那一个
for(int j=1;j<i;j++)
if(a[j]<a[i])
f[i]=max(f[i],f[j]+1);
最后的f[1-n]就是以每个数结尾的上升子序列的最大长度 只需要在里面再维护一个max即可
这个思想和kmp模式串内部求next数组很像
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],f[N];
int n;
int main()
{
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])
f[i]=max(f[i],f[j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[i]);
cout<<res;
return 0;
}
输出路径
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],f[N];
int g[N];//记录路径
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
f[i]=1;
g[i]=0;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
if(f[j]+1>f[i]){
f[i]=f[j]+1;
g[i]=j;
}
}
}
}
int k=1;//记录最优解的下标
for(int i=1;i<=n;i++)
if(f[k]<f[i])
k=i;
cout<<f[k]<<endl;
//可倒推路径 一共是f[k]个值
for(int i=0,len=f[k];i<len;i++){
cout<<a[k]<<" ";//首先k是答案所在的位置 a[k]保存的就是路径
k=g[k];//g[k]记录的是从哪走到k位置 所以让k往上一个退（类似next数组）
}
return 0;
}
💬 评论