posts - 99,  comments - 8,  trackbacks - 0
grids 2757 求最大子例长度
//动态规划题目最重要的一点是如何将问题分解得到子问题，并且将子问题解决
//本题以下标为状态量，找到以该下标位置 i 为终点时的最长子列：如果 i 位置的值 > i - 1位置的值，则长度加 1 ，
//所以利用判断大小来递归，出口是：下表为 0 时，长度为 1
//利用 nMaxLen【i】记录长度避免了重复计算

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
    int n;
    int b[1000];
    int nMaxLen[1000];
    while (scanf ("%d", &n) != EOF && 1 <= n && n <= 1000)
    {
          memset (nMaxLen, 0 ,sizeof(nMaxLen));
          //将输入的数值存入数组 b 中 
          for (int i = 0; i < n; i ++)
          {
              scanf ("%d", &b[i]);
          }
          
          //找到每一个状态下标 i 对应的最大子列长度，并将其存入数组nMaxLen[]中
          nMaxLen[0] = 1;
          for (int i = 1; i < n; i ++)   
          {
              int temp = 0;
              for (int j = 0; j < i ; j ++)
              {
                  if ( b[i] > b[j])
                  {
                       if (temp < nMaxLen[j])          //只有当当前的长度 <  之前一位数的序列长时才可以赋值，最后起到 temp + 1 的作用     
                                                                                            // 为什么:最大序列可能出现在 j 之后如： 7    9    10     6     11
                       temp = nMaxLen[j];
                  }
              }
              nMaxLen[i] = temp + 1;
          }
          
          //遍历数组nMaxLen从中读出最大值，即：在该位置时取得最大的子序列
          int max = -1;
          for (int i = 0; i < n; i ++)
          {
              if (nMaxLen[i] > max)
              max = nMaxLen[i];
          } 
          
          printf ("%d\n", max);
    }
    //system ("pause");
    return 0;
}
posted on 2010-08-14 15:38 雪黛依梦 阅读(189) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


Copyright ©2025 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2010年8月>
日一二三四五六
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜