PHP求最大子序列和的算法实现

给定整数：A1 A2 A3 A4 … An,其中可能有负数，求Ai-Aj的和的最大值。

 
<?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; 
?>