When will the most powerful brain Kim Soo-hyun be broadcast? Implementation of the algorithm for finding the maximum sum of subsequences in PHP

Copy the 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 incomplete is a negative number, the first item of the maximum subsequence must be a positive number, otherwise the sum of the numbers after the maximum subsequence plus the negative number of the first item is definitely not the maximum; 3. If the entire sequence is negative, then the maximum The sum of the subsequences is 0;
//The all-negative sequence is very simple, no example
$arr=array(4,-3,5,-2,-1,2,6,-2);
function getmaxsum($ arr){
$thissum=0;
$maxsum=0;
$start=0;//Record the starting subscript of the subsequence
$end=0;//Record the ending subscript of the subsequence
for($ i=0;$i$thissum+=$arr[$i];//Get the sum of the current subsequence
if($thissum>$maxsum){//If the current The sum of subsequences is greater than the sum of the current maximum subsequence
$maxsum=$thissum; //Change the sum of the current maximum subsequences
$end=$i;
}else if($thissum<0){//If the current subsequence If the sum of the sequence 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;
?>

The above has introduced the implementation of the algorithm for finding the maximum subsequence sum in PHP, including the content of The Most Powerful Brain Kim Soo-hyun. I hope it will be helpful to friends who are interested in PHP tutorials.