$O(n\log{n})$ Approach is needed.

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n;i++)
        cin >> a[i];

    int lis = 0;
    vector<int> dp(n, INT_MAX);

    for (int i = 0; i < n; i++){
        auto k = lower_bound(dp.begin(), dp.end(), a[i]);
        
        if (*k == INT_MAX)
            lis++;
        
        *k = min(*k, a[i]);
    }

    cout << lis << '\n';
}