算法 贪心 二分

算法分析（最长严格上升子序列）：每次将要插入的数字放在小于它的最大的数的后面

子序列的长度len=max(len,二分出来的位置+1)

时间复杂度 $O(nlogn)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std ;

const int N = 100010 ;

int q[N] ;
int g[N] ;
int n ;

int main(){
    cin >> n ;
    for(int i=0;i<n;i++){
        cin >> q[i] ;
    }

    int len = 0 ;
    g[0] = -2e9 ;//g[0]是最长上升子序列的哨兵，要比所有的数字小
    for(int i=0;i<n;i++){
        int l = 0,r = len ;
        while(l<r){//二分出小于当前数字的最大数
            int mid = l + r + 1 >> 1 ;
            if(g[mid]<q[i]) l = mid ;
            else r = mid - 1 ;
        }
        len = max(r+1,len) ;
        g[r+1] = q[i] ;//最长上升子序列对应的区间为1~len
    }
    cout << len << endl ;
    return 0 ;
}