题目链接：
https://www.luogu.com.cn/problem/P1020

参考：
http://www.cnblogs.com/GodA/p/5180560.html
https://www.luogu.com.cn/blog/w1049/solution-p1020

题解：
第一行：
为从1到n的最长非升子序列的个数。
第二行：
Dilworth定理：偏序集能划分成的最少的全序集的个数==最大反链的元素个数。
故为从1到n最长单调升序列的个数。

DP
O(n^2)：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e5 + 5;

int a[MAXN];
int f[MAXN];
int p[MAXN];

int main(){
// freopen("test.in","r",stdin);
// freopen("test1.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int ans=1;
	int tot=1;
	int n=0;
	while(cin>>a[++n]);
	for(int i=1;i<n;i++){
		f[i]=1;
		p[i]=1;
		for(int j=1;j<i;j++){
			if(a[i]<=a[j]) f[i]=max(f[i],f[j]+1);
			if(a[i]>a[j]) p[i]=max(p[i],p[j]+1);
		}
		ans=max(ans,f[i]);
		tot=max(tot,p[i]);
	}
	cout<<ans<<endl;
	cout<<tot<<endl;	
	return 0;
}

二分+贪心
O(nlogn)：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e5 + 5;

int a[MAXN];
int f1[MAXN];
int f2[MAXN];

int main(){
// freopen("test.in","r",stdin);
// freopen("test3.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int len1=1,len2=1,n=0;
	while(cin>>a[++n]) ;
	f1[1]=f2[1]=a[1];
	for(int i=2;i<n;i++){
		if(a[i]<=f1[len1]){
			f1[++len1]=a[i];
		}else{
			*upper_bound(f1+1,f1+1+len1,a[i],greater<int>() )=a[i];
		}
		if(a[i]>f2[len2]){
			f2[++len2]=a[i];
		}else{
			*lower_bound(f2+1,f2+1+len2,a[i])=a[i];
		}
	}
	cout<<len1<<endl;
	cout<<len2<<endl;
	return 0;
}