题目描述

blablabla

样例

算法1

(动态规划)

C++ 代码

#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
int dp[1005];//表示以num[i]为结尾的子序列的长度 
int main(){
    int n;
    cin>>n;
    int num[n];
    for(int i = 0;i < n;i++){
        cin>>num[i];
    }
    memset(dp,0,sizeof(dp));
    for(int i = 0;i < n;i++){
        dp[i] = 1;//首先初始化为1； 
        for(int j = 0;j < i;j++){
            if(num[i] > num[j]){
                dp[i] = max(dp[i],dp[j]+1); 
            }
        }
    }
    int len = 0;
    for(int i = 0;i < n;i++)len = max(len,dp[i]);
    cout<<len<<endl;
    return 0;
}