题目分析

这题不就是求有多少个上升子序列吗。

导弹拦截（大佬请自动忽略）。

这题就是暴力，但是如果从 $1-ans$ 暴力一遍时间复杂度为 $O(n^2)$，会超时，那怎么办呢？有了用二分就能完美避免这个问题，现在时间复杂度为 $O(n \log n)$，最后输出 $ans$ 就行啦。

代码！

#include<bits/stdc++.h>
using namespace std;
int n,x,k,ans;
int a[100005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		k=upper_bound(a+1,a+ans+1,x,greater<int>())-a;//二分
		if(k>ans){//比较
			a[++ans]=x;	
		}
		else{
			a[k]=x;
		}
	}
	cout<<ans;//输出
	return 0;//好习惯
}

下期见！