LIS(最长递增子序列) 二分 + dp

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 998244353
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int N = 100010;
int n;
int a[N], q[N];
// q[i] 表示长度为 i 的上升子序列的末尾元素最小为 q[i]
void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) scanf("%d", 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;
    }
    // 可以把当前这个数放在长度为 r 的上升子序列后面 所以长度为 r + 1
    len = max(len, r + 1); 
    //因为找到的是 小于 a[i] 的上升子序列的长度最大值 所以 q[r + 1] 一定比 a[i] 大 那么更新 q[r + 1] 为 a[i] 不会改变长度 且后续有更多的空间放后面的数
    q[r + 1] = a[i]; 
  }
  printf("%d\n", len);
}
int main() {
  //int t; cin >> t;
  //while (t--)
    solve();
  return 0;
}