jake1036

动态规划法-------最大连续子序列和

                 动态规划法解决最大连续子序列和

     问题描述 :
       数组 int a[] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ; 某几个连续的子序列其和最大,比如a0+a1 = -1 。a1+a2+a3+a4 = 78 。则a1 a2 a3a4组成的数组即是所求。
      


     解决方法:
        此题尝试使用动态规划的方法进行解决,首先建立状态方程。
       设b[j]表示第j处,以a[j] 结尾的子序列的最大和。
       则b[j] = max(a[j] + b[j-1] , a[j]) ,而我们的所求的答案,就是从1- n对b数组求最大值。
    

 代码如下:
      

  
/*
 最大连续字段和 时间复杂度为O(N) 
 定义b[j]为数组中包含a[j]的最大连续子序列和
 注意一个误区,b[j] 并不是1-j中最大的连续子序列的和,只是包含a[j]的最大子序列的和 
 而我们所要求的是求出b[j]中最大的值,即为所求 

 状态方程为: b[j] = max(b[j-1] + a[j] , a[j]) 
*/

#include 
<iostream>
 
using namespace std ;
 
const int N = 8 ;
 
int a[] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ;
 
int b[N] ; //b[i]表示包含a[i]的最大连续子序列之和 
 inline int max(int a , int b) 
 
{
   
return (a > b) ? a : b ;       
 }

 
int main()
 
{
   b[
0= a[0] ;  
   
int i , mam = b[0];   
   
for(i = 1;  i < N ; i++)
   

     b[i] 
= max(a[i] , b[i-1+ a[i]);   
     
if(mam < b[i])
       mam 
= b[i] ;     
   }

   printf(
"max %d\n" , mam) ;
   
   
for(i = 0;  i < N ; i++)   
     printf(
"%d\n" , b[i]) ;
   system(
"pause") ;    
   
return 0 ;  
 }

  

posted on 2011-04-21 13:54 kahn 阅读(9572) 评论(3)  编辑 收藏 引用 所属分类: 算法相关

Feedback

# re: 动态规划法-------最大连续子序列和[未登录] 2013-04-10 17:20 123

感觉这个是错的吧 b[j] = max(a[j] + b[j-1] , a[j])   回复  更多评论   

# re: 动态规划法-------最大连续子序列和[未登录] 2013-04-10 17:24 123

比如这种情况
-1 -1 9 9 9 -1 -1

-1 -1 9 9 9 -1 -1 9

b[7] == 27
按照你的公式
b[8] == 36 而事实上等于 34  回复  更多评论   

# re: 动态规划法-------最大连续子序列和 2013-10-05 06:41 456

@123
谁说的,明明b[7] == 25好吧  回复  更多评论   



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