题解

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int INF = 0x3f3f3f3f;
int n = 0, ma, d[N], a[N], k, x[N], xl = 1, t, len = 1;
int main(){
	x[1] = INF;
	while(cin>>a[++n]);
	d[1] = a[1];
	for (int i = 2;i <= n;i++){
		if (a[i] <= d[len]) d[++len] = a[i];
		else d[upper_bound(d + 1, d + len + 1, a[i], greater<int>()) - d] = a[i];
	}
	cout<<len - 1<<endl;
	for (int i = 1;i <= n;i++){
		t = 0;
		if (x[xl] < a[i]){
			xl++;
			x[xl] = a[i];
		}
		else{
			int k = lower_bound(x + 1,x + xl + 1,a[i]) - x;
			x[k] = a[i];
		}
	}
	cout<<xl<<endl;
	return 0;
}

经典题型