PHP求最大子序列和的算法實(shí)現(xiàn)
更新時(shí)間: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、如果整個(gè)序列不全是負(fù)數(shù),最大子序列的第一項(xiàng)必須是正數(shù),否則最大子序列后面的數(shù)加起來(lái)再加上第一項(xiàng)的負(fù)數(shù),其和肯定不是最大的;3、如果整個(gè)序列都是負(fù)數(shù),那么最大子序列的和是0;
//全負(fù)數(shù)序列很簡(jiǎn)單,不舉例
$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,則把下一個(gè)元素值假定為最大子序列的第一項(xiàng),這里可以保證最大自序列的第一項(xiàng)一定是正數(shù)
$thissum=0;//前提這個(gè)序列不全是負(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;
?>
您可能感興趣的文章:
- PHP寫楊輝三角實(shí)例代碼
- 深入理解PHP幾個(gè)算法:PHP冒泡、PHP二分法、PHP求素?cái)?shù)、PHP乘法表
- php 3行代碼的分頁(yè)算法(求起始頁(yè)和結(jié)束頁(yè))
- php實(shí)現(xiàn)猴子選大王問(wèn)題算法實(shí)例
- PHP貪婪算法解決0-1背包問(wèn)題實(shí)例分析
- php約瑟夫問(wèn)題解決關(guān)于處死犯人的算法
- PHP基于回溯算法解決n皇后問(wèn)題的方法示例
- PHP使用棧解決約瑟夫環(huán)問(wèn)題算法示例
- PHP基于遞歸算法解決兔子生兔子問(wèn)題
- PHP實(shí)現(xiàn)的解漢諾塔問(wèn)題算法示例
- PHP實(shí)現(xiàn)的楊輝三角求解算法分析
相關(guān)文章
php中ob(Output Buffer 輸出緩沖)函數(shù)使用方法
php中ob(Output Buffer 輸出緩沖)函數(shù)使用方法...2007-07-07基于php實(shí)現(xiàn)的驗(yàn)證碼小程序
本文主要介紹了基于php實(shí)現(xiàn)的驗(yàn)證碼小程序的具體實(shí)現(xiàn)方法,并做了詳細(xì)注釋,有利于理解與學(xué)習(xí),需要的朋友一起來(lái)看下吧2016-12-12PHP中使用json數(shù)據(jù)格式定義字面量對(duì)象的方法
這篇文章主要介紹了PHP中使用json數(shù)據(jù)格式定義字面量對(duì)象的方法,這是一種變通方法,使用json還可以在類中生成數(shù)組哦,需要的朋友可以參考下2014-08-08一致性哈希算法以及其PHP實(shí)現(xiàn)詳細(xì)解析
以下是對(duì)用PHP實(shí)現(xiàn)一致性哈希算法進(jìn)行了詳細(xì)的介紹,需要的朋友可以過(guò)來(lái)參考下2013-08-08深入分析使用mysql_fetch_object()以對(duì)象的形式返回查詢結(jié)果
本篇文章是對(duì)使用mysql_fetch_object()以對(duì)象的形式返回查詢結(jié)果進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-06-06PHP實(shí)現(xiàn)的簡(jiǎn)單在線計(jì)算器功能示例
這篇文章主要介紹了PHP實(shí)現(xiàn)的簡(jiǎn)單在線計(jì)算器功能,涉及php數(shù)值運(yùn)算與表單操作相關(guān)技巧,需要的朋友可以參考下2017-08-08