程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> PHP綜合 >> PHP求最大子序列和的算法實現

PHP求最大子序列和的算法實現

編輯: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;
?>
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved