Home  >  Article  >  php教程  >  正负数数组最大子序列

正负数数组最大子序列

WBOY
WBOYOriginal
2016-06-06 19:33:391912browse

给出数组,该数组由正负数字组成,找出该数组中连续元素组成的子数组的最大值。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){

给出数组,该数组由正负数字组成,找出该数组中连续元素组成的子数组的最大值。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 ) 
Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn