Algorithm implementation for finding the maximum sum of subsequences in PHP_PHP tutorial

Copy code The code is as follows:

//Author: Distant Expectation
//QQ: 15624575
//Algorithm analysis: 1. It must be an integer sequence. 2. If the entire sequence is not all negative numbers, the first item of the maximum subsequence must be a positive number, otherwise the numbers after the maximum subsequence are added together with the first If the term is a negative number, its sum is definitely not the largest; 3. If the entire sequence is negative, then the sum of the largest subsequence is 0;
//The all-negative sequence is very simple, no examples
$arr=array( 4,-3,5,-2,-1,2,6,-2);
function getmaxsum($arr){
$thissum=0;
$maxsum=0;
$start=0;//Record the starting index of the subsequence
$end=0;//Record the ending index of the subsequence
for($i=0;$i$thissum+=$arr[$i];//Get the sum of the current subsequence
if($thissum>$maxsum){//If the sum of the current subsequence is greater than the current maximum subsequence The sum of the sequence
$maxsum=$thissum;//Change the sum of the current maximum subsequence
$end=$i;
}else if($thissum<0){//If the sum of the current subsequence If the sum is less than 0, the next element value is assumed to be the first item of the largest subsequence. Here it can be guaranteed that the first item of the largest self-sequence must be a positive number
$thissum=0;//The premise is that this sequence is not all negative numbers
$start=$i+1;
}
}
$parr=array($start,$end,$maxsum);
return $parr;
}
list($start,$end,$maxsum)=getmaxsum($arr);
echo 'The maximum subsequence is:';
for($i=$start;$i<=$end;$i++ ){
echo $arr[$i].' ';
}
echo '
';
echo 'The sum of the maximum subsequence is'.$maxsum;
?>

http://www.bkjia.com/PHPjc/323639.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/323639.htmlTechArticleCopy the code as follows: ?php //Author: Distant Expectation//QQ:15624575 //Algorithm Analysis: 1. It must be a sequence of integers. 2. If the entire sequence is not all negative numbers, the first of the largest subsequence...