板子题

/*
 * @Author: YMYS
 * @Date: 2024-02-25 21:38:22
 * @LastEditTime: 2024-12-18 17:48:29
 * @FilePath: \VScode-C&C++-Coding\z_demo\easy.cpp
 * @URL:https://www.acwing.com/problem/content/897/
 * @Description: 895. 最长上升子序列
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

// int T;
// void solve(){

// }

//dp[i]表示以w[i]结尾的最长子序列的长度的值
int n, w[N], dp[N];

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    // cin>>T;
    // while(T--){
    //     solve();
    // }
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];

    //我们遍历每一个数
    for(int i=1;i<=n;i++){
        dp[i]=1;//最短的最长子序列长度为1

        //我们要遍历每一个w[i]前面的数，即 1 ~ (i-1)
        for(int j =1;j<i;j++){
            if(w[i] > w[j]){
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
    }

    //遍历整个数组，找出最大值
    int res = 1;
    for(int i=1;i<=n;i++){
        res = max(res, dp[i]);
    }

    cout<<res<<endl;

    return 0;
}