最长上升子序列-详解
首先考虑可以几维表示。
dp问题--->状态表示f[i]--->集合:所有以第i个数结尾的上升子序列,例如18,28,128等。
---->属性:集合里面每一个上升子序列的长度的最大值MAX
--->状态计算f[i]=max(f[j]+1),j=0,1,2,...,i-1
算法1
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int f[N],a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
f[i]=1;//每一个数的上升子序列起码等于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(f[i],res);
printf("%d\n",res);
return 0;
}
如果想要存下来怎么办
只需要加一个记录数组
C++代码如下
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int f[N],a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
f[i]=1;//每一个数的上升子序列起码等于1
g[i]=0;
for(int j=1;j<i;j++)//这个就是说明与之前的每个数进行比
{
if(a[j]<a[i])
if(f[i]<f[j]+1)
{
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;
printf("%d\n",f[k]);
for(int i=0,len=f[k];i<len;i++)
{
printf("%d ",a[k]);
k=g[k];
}
return 0;
}