题目描述 Description给一个数组a1, a2 ... an，找到最长的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。
输出长度即可。
输入描述 Input Description第一行，一个整数N。
第二行 ，N个整数（N < = 5000）
输出描述 Output Description输出K的极大值，即最长不下降子序列的长度
样例输入 Sample Input5
9 3 6 2 7
样例输出 Sample Output3
数据范围及提示 Data Size & Hint【样例解释】
最长不下降子序列为3,6,7
动态规划求逐步求出每一点的最大值。
附AC代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 5 int main(){ 6 7 int n,a[5010],dp[5010]; 8 while(cin>>n){ 9 int MAX=0; 10 for(int i=1;i<=n;i++){ 11 cin>>a[i]; 12 } 13 for(int i=1;i<=n;i++){ 14 for(int j=1;j<i;j++){ 15 if(a[j]<a[i]){//"!=" 16 dp[i]=max(dp[i],dp[j]+1); 17 MAX=max(MAX,dp[i]); 18 } 19 } 20 } 21 cout<<MAX+1<<endl; 22 } 23 } 24 /* 25 6 26 1 1 1 1 10 7 27 */
原文：http://www.cnblogs.com/Kiven5197/p/5696874.html