O(n^2)的解决方案

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

int n;
int dp[1010]; //dp[i] : 以a[i]结尾的最长严格上升子序列的长度值
int a[1010];
int main(){
    cin>>n;
    for(int i = 0;i<n;i++) scanf("%d",&a[i]);//读入数据
    for(int i = 0;i<n;i++){
        dp[i] = 1;
        for(int j = 0;j<i;j++){
            if(a[i] > a[j]){ //看是否可以在dp[j]扩展1位
                dp[i] = max(dp[i],dp[j]+1);//多次扩展，需要更新
            }
        }
    }
    cout<<*max_element(dp,dp+n)<<endl;
    return 0;
}

另外一个O(nlogn)解决方案

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

int n;
int dp[1010];//dp[e]：最长递增区间的末尾数字
int a[1010];
int main(){
    cin>>n;
    for(int i = 0;i<n;i++) scanf("%d",&a[i]);//读入数据
    dp[0] = a[0];//要维护的区间
    int e = 0;//区间末尾下标
    for(int i = 1;i<n;i++){
        if(a[i] > dp[e]) {//当前数大于区间末尾，就加入末尾
            dp[++e] = a[i];
        }else{
            int t = lower_bound(dp,dp+e+1,a[i])-dp;//否则就替换掉区间第一个大于等于a[i]的数
            dp[t] = a[i];
        }
    }
    cout<<e+1<<endl;


    return 0;
}