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

红太狼 2022-08-05 01:20 188阅读 0赞

## 记得有次去索尼还有一个啥公司忘了名字，都问到了这个问题，找了下答案，特此记录一下： ##

## 问题描述 ：   数组 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数组求最大值。    ##

## 代码如下：    ##

![ExpandedBlockStart.gif][] /\*  
![InBlock.gif][] 最大连续字段和 时间复杂度为O(N)  
![InBlock.gif][] 定义b\[j\]为数组中包含a\[j\]的最大连续子序列和  
![InBlock.gif][] 注意一个误区，b\[j\] 并不是1-j中最大的连续子序列的和，只是包含a\[j\]的最大子序列的和  
![InBlock.gif][] 而我们所要求的是求出b\[j\]中最大的值，即为所求  
![InBlock.gif][]  
![InBlock.gif][] 状态方程为: b\[j\] = max(b\[j-1\] + a\[j\] , a\[j\])  
![ExpandedBlockEnd.gif][]\*/   
![None.gif][]\#include  < iostream >   
![None.gif][] using  namespace  std ;  
![None.gif][] const  int  N  =  8  ;  
![ExpandedBlockStart.gif][] int  a\[\]  =  \{ \-4 , 3 ,56 , \-15 , 34 , 0 , \-14 , 4\}  ;  
![None.gif][] int  b\[N\] ;  // b\[i\]表示包含a\[i\]的最大连续子序列之和    
![None.gif][]  inline  int  max( int  a ,  int  b)  
![ExpandedBlockStart.gif][] \{  
![InBlock.gif][]return (a > b) ? a : b ;  
![ExpandedBlockEnd.gif][] \}   
![None.gif][] int  main()  
![ExpandedBlockStart.gif][] \{  
![InBlock.gif][] b\[0\] = a\[0\] ;  
![InBlock.gif][]int i , mam = b\[0\];  
![InBlock.gif][]for(i =1; i < N ; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] b\[i\] = max(a\[i\] , b\[i\-1\] \+ a\[i\]);  
![InBlock.gif][]if(mam < b\[i\])  
![InBlock.gif][] mam = b\[i\] ;  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][] printf("max %d\\n" , mam) ;  
![InBlock.gif][]  
![InBlock.gif][]for(i =0; i < N ; i\++)  
![InBlock.gif][] printf("%d\\n" , b\[i\]) ;  
![InBlock.gif][] system("pause") ;  
![InBlock.gif][]return0 ;  
![ExpandedBlockEnd.gif][] \}   
![None.gif][]  
![None.gif][]

[ExpandedBlockStart.gif]: /images/20220805/3a20f7e56d5647eea73427990cdf6995.png
[InBlock.gif]: /images/20220805/fcdcc54b52a343e18866232b7756e305.png
[ExpandedBlockEnd.gif]: /images/20220805/7c49f28b5b8d4fc6937cde6b9b2dd949.png
[None.gif]: /images/20220805/999573c4c97e4cdfaa823bbc23b66327.png
[ExpandedSubBlockStart.gif]: /images/20220805/5a4aaa291dd44cc7a7eba7f8de6b4625.png
[ExpandedSubBlockEnd.gif]: /images/20220805/be81983c03e5472d99a7febeb1129c41.png