896. 最长上升子序列 II

思想：贪心+二分(O(nlogn))
末尾小的lis比末尾大的lis更优，因为他有希望去更新出更长的最长上升子序列

b[i]表示长度为i的最长上升子序列中末尾元素的最小值，b[i]单调增（用二分的条件，这个东西要证明）

#include<iostream>
using namespace std;

const int N = 100010;

int a[N];
int b[N];
int n;

int main(){
    cin >> n;
    
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    int len = 0;
    for(int i = 0; i < n; i ++){
        int l = 0, r = len;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(b[mid] < a[i]) l = mid; // b[1 ~ mid] < a[i]
            else r = mid - 1;
        }
        len = max(len, l + 1);
        b[l + 1] = a[i];
    }
    
    cout << len << endl;
    return 0;
}