最长上升子序列

原版

#include<bits/stdc++.h>
using namespace std;
int n,ma;
int f[114514],arr[114514];
void out() {
	for(int i=1;i<=n;i++) {
		cout<<f[i]<<" ";
	}
	cout<<endl;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&arr[i]),f[i]++;
	for(int i=1;i<=n;i++) {
		ma=0;
		for(int j=1;j<i;j++) {
			if (arr[j]<arr[i]) ma=max(ma,f[j]);
		}
		f[i]+=ma;
		//out();
	}
	ma=0;
	for(int i=1;i<=n;i++) ma=max(ma,f[i]);
	cout<<ma;
}

优化版本（单调不升）

#include<bits/stdc++.h>
#define i64 long long
using namespace std;
i64 dp1[1145144],dp2[1145144],l[1145144];
vector<i64> arr;
int n,len,l1,l2;
int main()
{
	while(scanf("%d",&n)!=EOF) 
		arr.push_back(n);
	len=arr.size();
	dp1[1]=dp2[1]=arr[0];
	l1=1,l2=1;
	for(int i=1;i<len;i++) {
		if (arr[i]<=dp1[l1]) {
			dp1[++l1]=arr[i];
		} else {
			dp1[upper_bound(dp1+1,dp1+l1+1,arr[i],greater<i64>())-dp1]=arr[i];
		}
		if (arr[i]>dp2[l2]) {
			dp2[++l2]=arr[i];
		} else {
			dp2[lower_bound(dp2+1,dp2+l2+1,arr[i])-dp2]=arr[i];
		}
	}
	cout<<l1<<endl<<l2<<endl;
}