AcWing 896. 最长上升子序列 II-c++
原题链接
中等
作者:
硬拉tom
,
2021-02-05 17:10:40
,
所有人可见
,
阅读 341
算法1
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010;
int a[N],p[N],n;
int main(){
cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
int mid,idx=0;
p[0]=a[0];//贪心的维护一个递增的数组,且递增得越慢越好,每次找当前数的插入位置可以套二分有边界模板,最后这个数组数组长度就是答案
// 如原数组是:1 2 5 4 3 6 7, 贪心维护的这个数组最后是 1 2 3 6 7,
for(int i=1;i<n;i++){
int l=0,r=idx;
while(l<r){//二分又边界模板,找数组中恰好大于等于当前数的下标
mid=l+r>>1;
if(p[mid] >= a[i]) r=mid;
else l=mid+1;
}
if(p[l] < a[i]) {//维护数组中没有比当前数大的即加入维护数组尾部
p[l+1]=a[i];
idx=l+1;
}else {
p[l]=a[i];
}
}
cout << idx+1;
return 0;
}