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 )