jake1036

动态规划法-----最长增序子序列(非连续)

           动态规划法 求最长非连续增序子序列

    问题描述

  一个整形数组a[]= {1 ,7, 3, 5, 9, 4, 8}，其中a0 ，a1为一个递增子序列长度为2， a0 a2 a5 a6为一个递增序列，其长度为4，且为最长的递增子序列。

   解决方案

   设b[j]为以a[j]结束的最长递增序列的长度，则b[j] = max(b[k]) ，其中1<=k<j ,且a[k] < a[j] 。 问题的答案为max(b[j]) 1<= j <= n 。

   解决方法类似求最大连续子序列和的问题。
  


  代码如下

  
/*
  定义s[i] 表示第i个位置处，以a[i]为结尾的最大递增长度 
  先求每个位置处的最大长度，然后遍历求最大长度即可 
  下面一步增加一个存储结构，存储究竟是哪几个数组构成了递增的最大长度的数组 
*/

#include <iostream>
 using namespace std ;
 const int N = 1010 ;
 
 int s[N] ;
 int a[N]  ; 
 int p[N]  ; //p[i] 表示 以a[i]结尾的最长子串的前一个节点的标号 
 int main()
 {
   int n , i , k;
   scanf("%d" , &n) ;
   for(i = 0 ; i < n ;i++)
   {
     scanf("%d" ,&a[i]);
     s[i] = 1 ;
     p[i] = i ; //初始化每一个路径   
   }
   
   for(i = 0 ; i < n ; i++)  
    {
      for(k = 0 ; k < i ; k++)
       {
         if(a[i] > a[k])
         {
            int q = s[k] + 1 ;  
            if(s[i] < q) 
             {
               s[i] = q ;
               p[i] = k ;       
             }
         }             
       }         
    } 
   
   int max = 0 ;  
   for(i = 0 ; i < n ;i++)  
   {
    
       if(s[max] < s[i])  
          max = i ;     
   }
     printf("%d\n" , s[max]) ;

 
   while(1)
   {
    printf("%d->" , a[max]) ;      
    if(max == 0)
     break ;
    max = p[max] ;    
   }
   
     system("pause");
    return 0 ;   
 } 

posted on 2011-04-21 14:11 kahn 阅读(1887) 评论(3)  编辑 收藏 引用

Feedback

# re: 动态规划法-----最长增序子序列(非连续) 2011-08-10 17:14 wangyan

读师兄博客受益匪浅。。
PS：我觉得if(max == 0)
打印的时候应当改为if（max==P[max]）
不然的话，若增序列不是从第一个开始，比如100 1 2 3 4，就会死循环。  回复  更多评论   

# re: 动态规划法-----最长增序子序列(非连续) 2011-08-20 17:46 杜明

@wangyan
我的垃圾博客就怕误人子弟，我都是很随意的写的。
http://blog.csdn.net/v_JULY_v/
这个网址是csdn上一个大牛写的，非常好。各种算法还有分析。推荐你看看。  回复  更多评论   

# re: 动态规划法-----最长增序子序列(非连续) 2011-08-20 17:47 杜明

我的垃圾博客就怕误人子弟，我都是很随意的写的。
http://blog.csdn.net/v_JULY_v/
这个网址是csdn上一个大牛写的，非常好。各种算法还有分析。推荐你看看。  回复  更多评论   



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