acwing 896 最长上升子序列II

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
typedef long long LL ;
const LL N = 1e5 +10 ;
LL n ; LL a[N] ;
LL q[N] ;//用于记录当长度为i时最后结尾的数
 
int main(){
  cin >> n ;
  for(int i = 1 ; i <= n ; i ++) cin >>a[i] ;
  int len = 0 ;
    //用二分来找到当前第i个数在q数组中的 第一个大于第i个数的位置 ；
    // 找到以后对len 和 q[r+1] 进行更新 
    //为什么可以更新呢？这里用到了贪心的思想，对于每一个最长上升子序列 一定是结尾越小越好 ，而我们二分找到的就是他的直接前驱
  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 << endl ;
  return 0 ;
}