本文實例講述了PHP實現求連續子數組最大和問題2種解決方法。分享給大家供大家參考，具體如下：
問題描述
求子數組的最大和
題目描述：
輸入一個整形數組，數組里有正數也有負數。
數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。
求所有子數組的和的最大值。要求時間復雜度為O(n)。
關于連續子數組最大和這個問題，有兩種解法，一種是動態規劃
解法如下：
function getMaxSubSum($arr){
$curSum = $arr[0];
$maxSum = $arr[0];
for($i = 1; $i < count($arr); $i++){
if($curSum > 0) $curSum += $arr[$i];
else $curSum = $arr[$i];
if($curSum > $maxSum) $maxSum = $curSum;
}
return $maxSum;
}
還有一種是掃描法
function getMaxSubSum($arr){
$curSum = 0;
$maxSum = 0;
for($i = 0; $i < count($arr); $i++ ){
$curSum += $arr[$i];
if($curSum <= 0) $curSum = 0;
if($curSum > $maxSum) $maxSum = $curSum;
}
if($maxSum == 0){
$maxSum = $arr[0];
for($i = 1; $i < count($arr); $i++){
if($maxSum < $arr[$i] ) $maxSum = $arr[$i];
}
}
return $maxSum;
}
更多關于PHP相關內容感興趣的讀者可查看本站專題：《PHP數組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結》、《php字符串(string)用法總結》、《php常用函數與技巧總結》、《PHP錯誤與異常處理方法總結》、《PHP基本語法入門教程》、《php面向對象程序設計入門教程》、《php+mysql數據庫操作入門教程》及《php常見數據庫操作技巧匯總》
希望本文所述對大家PHP程序設計有所幫助。
【網站聲明】本站部分內容來源于互聯網,旨在幫助大家更快的解決問題，如果有圖片或者內容侵犯了您的權益，請聯系我們刪除處理，感謝您的支持！