线性DP $O(n^2)$

注意细节:

• f[i] 表示以a[i]结尾的所有子序列的集合中，序列最大长度
• 这里每次从[0-i)开始扫描，故a[0]要初始化为负无穷

C++ 代码

#include<iostream>
using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)

int N;
int a[1003],f[1003];
const int INF=1e9;

int main(){
    cin>>N;
    ffor(i,1,N+1) scanf("%d",&a[i]);

    a[0]=-INF;
    ffor(i,1,N+1) //遍历每个结尾
        ffor(j,0,i)//在当前结尾的前面查找可以拼接的位置，选一个最大更新自己
        if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);

    //从结果中遍历检索结果    
    int res=-INF;
    ffor(i,1,N+1) res=max(res,f[i]);
    cout<<res<<endl;

    return 0;
}