问题是给出数组，该数组由正负数字组成，找出该数组中连续元素组成的子数组的最大值。下面是PHP实现的示例,需要的朋友可以参考下。

php实现正负数数组最大子序列，要求给出数组，该数组由正负数字组成，找出该数组中连续元素组成的子数组的最大值。

这其实得算是个背包变种吧，代码如下:

1. <?php 
2. $list = array(1,-3,-5,-7,8,9,-11,5); 
3.  
4. $cur = 0; 
5. $term = 0; 
6. $res = 0; 
7. $begin = 0; 
8.  
9. foreach($list as $k => $v){ 
10.  $cur += $v; 
11.  if($cur < 0){ 
12.   $cur = 0; 
13.   $begin = $k + 1; 
14.  }  
15.  if($cur > $res){ 
16.   $res = $cur; 
17.   $term = $k; 
18.  } 
19. } 
20. $max_seq = array_slice($list, $begin, ($term - $begin) + 1); 
21.  
22. echo $res . ','; 
23. print_r($max_seq); 
24. //17,Array ( [0] => 8 [1] => 9 )  

Tags: php正负数数组

分享到：