AcWing 896. 最长上升子序列 II
原题链接
中等
作者:
MNIST
,
2022-04-20 20:40:05
,
所有人可见
,
阅读 152
#include<iostream>
using namespace std;
const int N = 100010;
int q[N], a[N];
//遍历a[i],数组q[i]表示长度为i的所有上升子序列的集合,属性是集合尾数的最小值;这个数组的长度就是答案。
//二分法,在q中寻找最大的小于a[i]的q[r],那么长度为r+1的所有递增子序列的最小尾数更新为a[i],因为原先的q[r+1]一定大于等于a[i]
//如果r=len,说明要更新数组q的长度(更新答案),即len=max(len, r+1);否则答案不变
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){
//思路:只要a[i]比长度为len的所有子序列的最后一个数的最小值大,以a[i]结尾的所有上升子序列的长度至少为len+1
//二分,最后一个小于a[i]的数,更新len和q[r+1]
int l = 0, r = len;
while(l < r){
int mid = l+r+1 >> 1;
if(q[mid] >= a[i]) r = mid - 1;
else l = mid;
}
len = max(len, r+1);
q[r+1] = a[i];
}
cout<<len<<endl;
return 0;
}