复习xxx

/*
 * @Author: YMYS
 * @Date: 2024-02-25 21:38:22
 * @LastEditTime: 2024-12-16 22:19:26
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\5.第五章\2.线性DP\try.cpp
 * @URL:https://www.acwing.com/problem/content/898/
 * @Description: 最长上升子序列 II
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
int n;
int a[N];
vector<int> dp;

signed 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>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    dp.push_back(a[0]);

    for(int i=1;i<n;i++){
        if(a[i] > dp.back()) dp.push_back(a[i]);
        else *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }

    cout<<dp.size()<<endl;

    return 0;
}