Increasing Subsequence

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int n; cin >> n;
    10    vector<int> v(n);
    11    for (int i = 0; i < n; i++) cin >> v[i];
    12    vector<int> ans;
    13    for (int i = 0; i < n; i++) {
    14        if (ans.empty() || v[i] > ans.back()) {
    15            ans.push_back(v[i]);
    16        } else {
    17            int pos = lower_bound(ans.begin(), ans.end(), v[i]) - ans.begin();
    18            ans[pos] = v[i];
    19        }
    20    }
    21    cout << ans.size() << '\n';
    22    return 0;
    23}