a[N] 输入的序列
q[N] q[i] 表示长度为i的严格单调上升序列的结尾最小值
遍历a[N]
用二分法找当前长度len中 q[0]到q[len]中小于a[i]的最大值,更新q[r+1], 同时更新len
以
7
3 1 2 1 8 5 6
为例
q[1] = 3 len = 1
q[1] = 1 len = 1
q[2] = 2 len = 2
q[3] = 8 len = 3
q[3] = 5 len = 3
q[4] = 6 len = 4
后更新的数字是否影响结果?
答: 不会, 比如 1 3 6 2
最终q[n] 是 1 2 6 ,但是实际序列 是1 3 6 ,但是 1 3 6 还是 1 2 6 长度都是3,
更新了小于len的位置, 最多是没有后续,比如q[n] 更新到1 2 6停止了
但是len是3 (来自 1 3 6)是没有问题的
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], q[N];
int main() {
int n;
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 (q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len , r + 1);
q[r + 1] = a[i];
}
cout << len << endl;
}