WIKIOI-1576 最长不下降子序列

题目描述 Description
给一个数组a1, a2 … an，找到最长的不下降子序列ab1

输出长度即可。

输入描述 Input Description
第一行，一个整数N。

第二行 ，N个整数（N

输出描述 Output Description
输出K的极大值，即最长不下降子序列的长度

样例输入 Sample Input
5

9 3 6 2 7

样例输出 Sample Output
3

数据范围及提示 Data Size & Hint
【样例解释】

最长不下降子序列为3,6,7

本题是经典的动态规划练习题（代码有错误，已修改，感谢hpuhjl指出错误！）
//一般方法（非动态规划的方法）。动态规划方法暂时没写，会在以后写出来

#include
#include
#include
int num[5010],lin[5010];
int Fun(int n)
{
   int i,j,max;
   for(i=0;i   lin[i]=1;
   for(i=1;i   {
      for(j=0;j      if(num[i]>num[j]&&lin[i]      lin[i]=lin[j]+1;
   }
   
   max=-1;
   for(i=0;i   if(lin[i]>max)
   max=lin[i];
   return max;
}
int main()
{
    int i,j,n,m;
    scanf("%d",&n);
    for(i=0;i    {
      scanf("%d",&num[i]);
    }
    printf("%dn",Fun(n));
    return 0;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net