PROG-1151: ต้นไม้ (Tree)

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int N = 2e5 + 10;
int dp[N];

int main(){

    int n;
    scanf("%d", &n);

    int sz = 0;

    for(int i=1;i<=n;i++){
        int x;
        scanf("%d", &x);
        if(x > dp[sz]){
            sz ++;
            dp[sz] = x;
        }
        else {
            int l = 1, r = sz, mid, mn = INF;
            while(l <= r){
                int mid = (l + r) / 2;
                if(dp[mid] >= x){
                    mn = min(mn, mid);
                    r = mid - 1;
                }
                else
                    l = mid + 1;
            }
            dp[mn] = x;
        }
    }

    printf("%d", sz);

    return 0;
}