题目描述 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
解题思路：
应该算是序列型DP的最入门的写法了，严格上升子序列的写法有很多种，我用的这个还算是比较好理解的，题目中做了别样的处理就是为了防止出现某个序列，这个序列中的所有元素都是相同的，那么输出的就是1。。。
代码：
# include<cstdio>
# include<iostream>
using namespace std;
# define MAX 100000+4
int value[MAX];
int dp[MAX];
int main(void)
{
int n;
while ( cin>>n )
{
int flag = 0;
double sum = 0;
for ( int i = 0;i < n;i++ )
{
cin>>value[i];
sum+=value[i];
dp[i] = 1;
}
int tag = 0;
double avg = (1.0*sum)/n;
for ( int i = 0;i < n;i++ )
{
if ( value[i] == avg )
tag++;
}
if ( tag == n )
{
flag = 1;
}
int ans = 0;
for ( int i = 0;i < n;i++ )
{
for ( int j = i+1;j < n;j++ )
{
if ( value[j] > value[i] )
{
dp[j] = max( dp[j],dp[i]+1 );
ans = max( ans,dp[j] );
}
}
}
if ( flag )
{
cout<<value[1]<<endl;
}
else
cout<<ans<<endl;
}
return 0;
}