//每一类不一定都存在，如果不存在就跳过
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int arr[N],f[N];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin>>arr[i];
    }
    for (int i = 1; i <= n; i ++ )
    {
        f[i]=1; //只有他自己的时候就是1
        for (int j = 1; j < i; j ++ )
        {
            if(arr[j]<arr[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;
}

输出路径

//每一类不一定都存在，如果不存在就跳过
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int arr[N],f[N];
int path[N];    //存储路径
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin>>arr[i];
    }
    for (int i = 1; i <= n; i ++ )
    {
        f[i]=1; //只有他自己的时候就是1
        for (int j = 1; j < i; j ++ )
        {
            if(arr[j]<arr[i])
            {
                if(f[i]<f[j]+1)
                {
                    f[i]=f[j]+1;
                    path[i]=j;      //i是由j更新过来的
                }
            }
        }
    }
    int k=1;
    for (int i = 2; i <= n; i ++ )
    {
        if(f[k]<f[i])
        {
            k=i;
        }
    }
    cout<<f[k]<<endl;
    //输出路径
    for (int i = 0,len=f[k]; i < len; i ++ )
    {
        cout<<arr[k]<<' ';
        k=path[k];
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int arr[N];
int f[N];
int n;

int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ ) cin>>arr[i];
    for (int i = 1; i <= n; i ++ )
    {
        f[i]=1;
        for (int j = 1; j < i; j ++ )
        {
            if(arr[j]<arr[i]) f[i]=max(f[i],f[j]+1);
        }
    }
    //最后遍历一遍找到最大值，因为最后一个不一定就是最大的
    int ans=0;
    for (int i = 1; i <= n; i ++ ) ans=max(ans,f[i]);
    cout<<ans;
}