思路 ：

$f[i]$表示长度为$len$的最长上升子序列的最后一个数。

结尾越小越有利。

如果$a[i]$大于长度为$len$的最后一个数，就加上它，于是长度加1，

长度加1后的最后一个数就是$a[i]$。

否则，二分找到第一个大于它的替换掉末尾的数。

最后，输出$len$。

(贪心加二分) $O(nlogn)$

#include <bits/stdc++.h>

using namespace std ;

const int N = 100001 ;

int n ;
int len = 1 ;
int f[N] ;
int a[N] ;

int main ( ) {

    cin >> n ;
    for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;

    f[1] = a[1] ;

    for ( int i = 2 ; i <= n ; i ++ ) {

        if ( a[i] > f[len] ) f[++ len] = a[i] ;

        else  f[lower_bound ( f + 1 , f + 1 + len , a[i] ) - f] = a[i] ;

    }

    cout << len ;

    return 0 ;

}