选择去维护一个最小区间

代码1：

#include<bits/stdc++.h>
using namespace std;
int main() {int n;cin>>n;int num;vector <int> v;int res=0;for(int i=0;i<n;i++){cin>>num;int loc=v.size();int left=0;int right=v.size()-1;while(left<=right){int mid=(left+right)/2;if(num>=v[mid]){left=mid+1;}else{loc=mid;right=mid-1;}}if(loc==v.size()){res++;v.push_back(num);}else{v[loc]=num;}}cout<<res;return 0;
}

代码2：

#include<bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;int x[100005];int cnt = 0;for (int i = 0; i < n; i++) {int y;cin >> y;int *p = lower_bound(x, x + cnt, y);if (p == x + cnt) {cnt++;}*p = y;}cout << cnt << endl;return 0;
}

代码3：

#include<bits/stdc++.h>
using namespace std;
int main() {int n;cin>>n;int num;vector <int> v;int res=0;for(int i=0;i<n;i++){cin>>num;auto loc=lower_bound(v.begin(),v.end(),num);if(loc==v.end()){res++;v.push_back(num);}else{*loc=num;;}}cout<<res;return 0;
}