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 )