PHP求最大子序列和的算法實現(xiàn)
更新時間：2011年06月24日 22:23:44 作者：
給定整數(shù)：A1 A2 A3 A4 … An,其中可能有負(fù)數(shù)，求Ai-Aj的和的最大值。
復(fù)制代碼 代碼如下:
<?php
//作者：遙遠(yuǎn)的期待
//QQ:15624575
//算法分析：1、必須是整數(shù)序列、2、如果整個序列不全是負(fù)數(shù)，最大子序列的第一項必須是正數(shù)，否則最大子序列后面的數(shù)加起來再加上第一項的負(fù)數(shù)，其和肯定不是最大的；3、如果整個序列都是負(fù)數(shù)，那么最大子序列的和是0；
//全負(fù)數(shù)序列很簡單，不舉例
$arr=array(4,-3,5,-2,-1,2,6,-2);
function getmaxsum($arr){
$thissum=0;
$maxsum=0;
$start=0;//記錄子序列的起始下標(biāo)
$end=0;//記錄子序列的結(jié)束下標(biāo)
for($i=0;$i<count($arr);$i++){
$thissum+=$arr[$i];//取得當(dāng)前子序列的和
if($thissum>$maxsum){//如果當(dāng)前子序列的和大于當(dāng)前最大子序列的和
$maxsum=$thissum;//改變當(dāng)前最大子序列的和
$end=$i;
}else if($thissum<0){//如果當(dāng)前子序列的和小于0，則把下一個元素值假定為最大子序列的第一項,這里可以保證最大自序列的第一項一定是正數(shù)
$thissum=0;//前提這個序列不全是負(fù)數(shù)
$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;
?>
相關(guān)文章
![php快速url重寫 更新版[需php 5.30以上]](http://img.jbzj.com/images/xgimg/bcimg0.png)
本代碼是在apache上的LoadModule rewrite_module modules/mod_rewrite.so運行成功后的操作,利用php代碼對網(wǎng)站url重定向為更復(fù)雜的邏輯結(jié)構(gòu)2010-04-04
PHP實現(xiàn)統(tǒng)計代碼行數(shù)小工具
這篇文章主要為大家詳細(xì)介紹了PHP實現(xiàn)統(tǒng)計代碼行數(shù)小工具，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-09-09
PHP實現(xiàn)的下載遠(yuǎn)程圖片自定義函數(shù)分享
這篇文章主要介紹了PHP實現(xiàn)的下載遠(yuǎn)程圖片自定義函數(shù)分享,本文直接給出實現(xiàn)代碼和,本文直接給出實現(xiàn)代碼和使用方法,需要的朋友可以參考下2015-01-01
使用explode函數(shù)，把要替換的字符串做為分割符號，然 后把兩個數(shù)組元素中間接上要換成的字符串，然后UPDATE一下就行了2012-01-01
php防止偽造數(shù)據(jù)從地址欄URL提交的方法
針對偽造的數(shù)據(jù)從URL提交的情況，首先是檢查前一頁來源，這個方法只能防止手動在瀏覽器地址欄上輸入的URL，目前覺得還是用POST的方法傳遞重要數(shù)據(jù)比較可靠2014-08-08
php獲取遠(yuǎn)程圖片的兩種 CURL方式和sockets方式獲取遠(yuǎn)程圖片
php獲取遠(yuǎn)程圖片的兩種:CURL方式和sockets方式獲取遠(yuǎn)程圖片,需要的朋友可以參考下。2011-11-11
這篇文章主要介紹了php刪除路徑下的所有文件夾和文件的代碼的相關(guān)資料(php清空目錄代碼),需要的朋友可以參考下2023-03-03
學(xué)習(xí)discuz php 引入文件的方法DISCUZ_ROOT
這是discuz中定義論壇安裝根目錄的一個常量。現(xiàn)在我們就來分析一下這個很簡單但是非常實用的常量。2009-06-06
這篇文章主要介紹了PHP實現(xiàn)顯示照片exif信息的方法,需要的朋友可以參考下2014-07-07
這篇文章主要介紹了PHP使用flock實現(xiàn)文件加鎖的方法,實例分析了flock文件鎖的使用技巧,需要的朋友可以參考下2015-07-07