复制代码 代码如下:

<?php

//作者：遥远的期待

//QQ:15624575

//算法分析：1、必须是整数序列、2、如果整个序列不全是负数，最大子序列的第一项必须是正数，否则最大子序列后面的数加起来再加上第一项的负数，其和肯定不是最大的；3、如果整个序列都是负数，那么最大子序列的和是0；

//全负数序列很简单，不举例

$arr=array(4,-3,5,-2,-1,2,6,-2);

function getmaxsum($arr){

$thissum=0;

$maxsum=0;

$start=0;//记录子序列的起始下标

$end=0;//记录子序列的结束下标

for($i=0;$i<count($arr);$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);

return $parr;

}

list($start,$end,$maxsum)=getmaxsum($arr);

echo '最大子序列是:';

for($i=$start;$i<=$end;$i++){

echo $arr[$i].' ';

}

echo '<br>';

echo '最大子序列的和是'.$maxsum;

?>