溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
怎么在PHP中求連續子數組的最大和？相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
問題描述
求子數組的最大和
題目描述：
輸入一個整形數組，數組里有正數也有負數。
數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。
求所有子數組的和的最大值。要求時間復雜度為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中求連續子數組的最大和的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
