php求正负数数组中连续元素最大值示例
问题是给出数组，该数组由正负数字组成，找出该数组中连续元素组成的子数组的最大值。下面是PHP实现的示例,需要的朋友可以参考下。
php实现正负数数组最大子序列，要求给出数组，该数组由正负数字组成，找出该数组中连续元素组成的子数组的最大值。
这其实得算是个背包变种吧，代码如下:
- <?php
- $list = array(1,-3,-5,-7,8,9,-11,5);
- $cur = 0;
- $term = 0;
- $res = 0;
- $begin = 0;
- foreach($list as $k => $v){
- $cur += $v;
- if($cur < 0){
- $cur = 0;
- $begin = $k + 1;
- }
- if($cur > $res){
- $res = $cur;
- $term = $k;
- }
- }
- $max_seq = array_slice($list, $begin, ($term - $begin) + 1);
- echo $res . ',';
- print_r($max_seq);
- //17,Array ( [0] => 8 [1] => 9 )