当前位置:Gxlcms > PHP教程 > 编写一个PHP函数。求任意n个正负整数里面最大的连续和,要求算法时间复杂度尽可能低。

编写一个PHP函数。求任意n个正负整数里面最大的连续和,要求算法时间复杂度尽可能低。

时间:2021-07-01 10:21:17 帮助过:4人阅读

header("content-type:text/html;charset=utf8");
//算法分析:
//1、必须是整数序列
//2、如果整个序列不全是负数,最大子序列的第一项必须是正数,
//否则最大子序列后面的数加起来再加上第一项的负数,其和肯定不是最大的;
//3、如果整个序列都是负数,那么最大子序列的和是0;
$arr=array(-2,1,3,9,-4,2,3,8,-3,-4,1,3);
$thissum=0;
$maxsum=0;
$start=0;//记录子序列的起始下标
$end=0;//记录子序列的结束下标
for($i=0;$i $thissum+=$arr[$i];//取得当前子序列的和
if($thissum>$maxsum){//如果当前子序列的和大于当前最大子序列的和
$maxsum=$thissum;//改变当前最大子序列的和
$end=$i;
}else if($thissum<0){//如果当前子序列的和小于0,则把下一个元素值假定为最大子序列的第一项,这里可以保证最大自序列的第一项一定是正数
$thissum=0;//前提这个序列不全是负数
$start=$i+1;
}
}
$parr=array($start,$end,$maxsum);
list($start,$end,$maxsum)=$parr;
print_r($arr);
echo '
';
echo '最大子序列是:';
for($i=$start;$i<=$end;$i++){
echo $arr[$i].' ';
}
echo '
';
echo '最大子序列的和是'.$maxsum;
?>

以上就介绍了 编写一个PHP函数。求任意n个正负整数里面最大的连续和,要求算法时间复杂度尽可能低。,包括了方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

人气教程排行