#include<iostream>
#include<vector>
#define MAX 1010
using namespace std;
vector<int> len;
// 这里我返回的满足len[k]>=val[i]且k最小的位置
// 和上文红色部分的描述是等价的,只是变成了更新len[k],而不是len[k+1]
int bisearch(int val){
int left=0, right=len.size()-1;
while(left<=right){
int mid = (left+right)>>1;
if(len[mid] < val) left = mid+1;
else right = mid-1;
}
return left;
}
int main(){
int n, val;
cin>>n;
for(int i=0; i<n; ++i){
cin>>val;
int k = bisearch(val);
if(len.size()==k) len.push_back(val);
else len[k] = val;
}
cout<<len.size()<<endl;
return 0;
}
二分查找用函数:
#include<iostream>
#include<algorithm>
#define MAX 1010
using namespace std;
int p[1010];
int main(){
int n, val;
cin>>n;
int cnt=0;
for(int i=0; i<n; ++i){
cin>>val;
int k = lower_bound(p,p+cnt,val)-p;
if(cnt==k) p[cnt++]=val;
else p[k] = val;
}
cout<<cnt<<endl;
return 0;
}