Longest Ordered Subsequence O(nlogn)解法 STL

维护一个单调队列，对于每一个新的元素：

如果大于队尾元素，补在后面；

否则替换掉最小的大于它的数，这里用二分查找，因此时间复杂度为logn

演示一下：

1 3 7 5 9 4 8
1
1 3
1 3 7
1 3 5
1 3 5 9
1 3 4 9
1 3 4 8

#include <iostream>
#include <algorithm>
using namespace std;
int a[1111],n,k,m;
int main(){
	cin >> n;
	for (int i(1);i<=n;i++){
		cin >> k;
		if ( k>a[m] ) a[++m]=k;
		else a[upper_bound(a+1,a+m,k)-a] = k;	
	}
	cout << m << endl;
	return 0;
}