最长上升子序列的n*log(n)的模板解法
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int len = 1;
int n,d[N],tail[N];
int find(int x){
int left = 1,right = len;
while(left<right){
int mid = left + right>> 1;
if(x <= tail[mid]) right = mid; //此题与模板有所不同,其需要找的是第一个和他相同的下标,不是最后一个
else left = mid + 1;
}
return left;
}
int main(){
cin>>n;
for(int i = 1;i<=n;i++){
cin>>d[i];
}
tail[1] = d[1];
for(int i = 2;i<=n;i++){
if(d[i]>tail[len]){//如果新插入的值比所维护的递增数组中任意一个元素都大
len++;
tail[len] = d[i]; //此时因为数组中加入一个最大值,所以上升子序列长度一定加1
}
else{//如果新插入的值比所维护的最大值小的话,就二分进行查找位置,修改第一个大于d[i]的那个元素的值,
int index = find(d[i]);
tail[index] = d[i];
}
}
cout<<len;
return 0;
}