最长上升子序列 贪心解法

我们对于每个上升子序列问题，最需要知道这个序列的最小结尾即可。
例如 1 3 2 ...
在查找长度为3的上升子序列中，从长度为2的更新， 1 3 或者 1 2 ，那么如果一个数可以放在3后面构成长度为3的序列，则一定也可以放在2后面，所以我们记录最小的即可。

例题：

Acwing 896. 最长上升子序列 II

参考代码：

#include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N];
int n;
int q[N];//存的是每个最长上升子序列的最小结尾

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