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

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

　　?>