1)n^2做法

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n;
int a[maxn];
int from[maxn];//记录前驱 
int dp[maxn];//到i为止的最长上升子序列长度
void output(int x)
{
    if(!x)return;
    output(from[x]);
    printf("%d ",a[x]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        from[i]=0;
        for(int j=1;j<i;j++)
            if(dp[j]+1>dp[i]&&a[i]>a[j])
                dp[i]=dp[j]+1,from[i]=j;
    }
    int id=0,ans=0;
    for(int i=1;i<=n;i++)
        if(ans<dp[i])ans=dp[i],id=i;
    printf("%d\n",ans);
    output(id); 
    return 0;
}

2)nlogn做法，只能求长度

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005,inf=0x3f3f3f3f;
int n;
int a[maxn];
int f[maxn];
//该序列中，上升子序列长度为i的上升子序列的最小末尾数值
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]=inf;
    f[1]=a[1];
    int len=1;
    for(int i=2;i<=n;i++)
    {
        int l=1,r=len,mid;
        if(a[i]>f[len])f[++len]=a[i];
        else{
            while(l<r)
            {
                mid=l+r>>1;
                if(f[mid]>a[i])r=mid;
                else l=mid+1;
            }
            f[l]=min(a[i],f[l]);
        }
    }
    printf("%d",len);
    return 0;
}