php求正负数数组中连续元素最大值示例

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 )