答案代码

#include<iostream>
using namespace std;
const int N=1010;
int a[N],b[N];//b[i]的意思是以a[i]为结尾的上升子序列的最大长度
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        b[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])b[i]=max(b[j]+1,b[i]);
//状态转移就是如果a[i]之前的a[j]<a[i]的话，那么我们就要证明这一项可以作为
//以a[i]结尾的上升子序列的倒数第二项咯，那么我们拿b[j]+1和当前的b[i]取一个较大值(b[j]由于j<i的远古没所以已
//经在之前的i轮中算过了)，不断的比，把a[i]之前的数全部都比完，我们的状态转移就完成了
        }
    }
    int maxx=0;
    for(int i=1;i<=n;i++)
    {
        maxx=max(maxx,b[i]);
    }
    cout<<maxx;
    return 0;
}

记录下最长子序列

#include<iostream>
using namespace std;
const int N=1010;
int a[N],b[N];//b[i]的意思是以a[i]为结尾的上升子序列的最大长度
int c[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int len=0;
    for(int i=1;i<=n;i++)
    {
        b[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
                if(b[i]<b[j]+1)
                {
                    b[i]=b[j]+1;
                    c[i]=j;//记录最优解的下标
                }
//我们用c[i]=j来记录下当前序列当中这个数是由哪个数转移过来的
//到时候我偶们输出最长子序列的时候就k=c[i]输出a[k]，然后k=c[c[i]],直到c[i]为零为止
        }
    }
    int k=1;
    for(int i=1;i<=n;i++)
    {
        if(b[i]>k)k=i;
    }
    cout<<b[k]<<endl;
    int cnt=0;
    int ac[N];
    while(k)
    {
        ac[++cnt]=a[k];
        k=c[k];
    }
//因为我们这里想要正序输出最长子序列，所以我们把倒序最长子序列先存到一个临时数组里面，然后记录一下它的长度
//最后我们再倒序输出这个数组就可以了
    for(int i=cnt;i>0;i--)cout<<ac[i]<<' ';
    return 0;
}