动规解法

#include<bits/stdc++.h> 
//万能头文件
using namespace std;
int n,a[1001],dp[1001],ans=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        dp[i]=1;
        //若未找到有小于 i的数，则dp[i](i的最大上升子序列)只有1(自己本身)
        for(int j=i-1;j>=1;j--){
            if(a[i]>a[j]){
                //若a[i]严格大于a[j]，那么符合题干中上升的定义
                dp[i]=max(dp[i],dp[j]+1);
                //dp[j]+1中dp[j]：指以j为结尾的最大上升子序列的长度;
                //dp[j]+1中+1:指加上i，i的长度只有1;
                //dp[i]:之前一次以i为结尾的最大上升子序列的长度；;
            }
        }
        ans=max(dp[i],ans);  
        //比较1-n中以谁为结尾的上升子序列最长
    }
    cout<<ans;
    return 0;
}