题目描述 Description
给一个数组a1, a2 ... an，找到最长的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。
输出长度即可。
输入描述 Input Description
第一行，一个整数N。
第二行 ，N个整数（N < = 5000）
输出描述 Output Description
输出K的极大值，即最长不下降子序列的长度
样例输入 Sample Input
5
9 3 6 2 7
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
【样例解释】
最长不下降子序列为3,6,7
有两种做法
一种是O(n^2)
The other one is O(log n)
We always use the second one
Because is faster than the first one
But how to do it?
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int s[100000]; int ans,n; int main() { scanf("%d",&n); for(int i=1;i<=n;++i) { int sum; scanf("%d",&sum); if(sum>s[ans]) s[++ans]=sum; else { int p=(lower_bound(s+1,s+ans+1,sum)-s); s[p]=sum; } } printf("%d",ans); return 0; }