最长上升子序列II

主要思路：贪心 + 二分

只需要记录下每个长度的最后一个数字的最小值存到q数组中（贪心思想），容易证明q数组一定单调递增，故可以用二分找到小于a[i]的最大的那个数对应的长度。不断维护q数组和最大长度len即可

用了lower_bound()代替二分，只是为了偷懒哈哈，其实二分还很菜

#include <iostream>
#include <algorithm>
using namespace std;

const int NN = 1e5 + 10;
int N;
int a[NN], q[NN];

int main(){
    cin >> N;
    for (int i = 1; i <= N; i ++) scanf("%d", &a[i]);
    int len = 1; // len 是最大上升子序列长度
    q[1] = a[1];q[0] = -2e9;
    for (int i = 2; i <= N; i ++){
        int j = lower_bound(q, q + len + 1, a[i]) - 1 - q; // q[j] 是 小于 a[i] 的最大的那个数
        len = max(len, j + 1);
        q[j + 1] = a[i];
    }

    cout << len;

    return 0;
}