PHP 求最大子序列和算法：Kadane 算法實作詳解

問題定義

給定整數序列（含正負數），找出連續子序列使其和最大。若全為負數，最大和定義為 0（空子序列）。

算法分析（Kadane 算法）

1. 遍歷陣列，維護 current_sum（以當前元素結尾的最大子序列和）與 max_sum（全域最大和）。
2. 若 current_sum > max_sum，更新 max_sum 並記錄結束索引。
3. 若 current_sum < 0，歸零並將起始索引設為下一位置（負數拖累後續和，不如重新開始）。
4. 單次遍歷 O(n) 完成，空間 O(1)。

PHP 程式碼實作

<?php
$arr = array(4, -3, 5, -2, -1, 2, 6, -2);

function getMaxSum($arr) {
    $thisSum = 0;
    $maxSum = 0;
    $start = 0;
    $end = 0;
    $tempStart = 0;

    for ($i = 0; $i < count($arr); $i++) {
        $thisSum += $arr[$i];

        if ($thisSum > $maxSum) {
            $maxSum = $thisSum;
            $end = $i;
            $start = $tempStart;
        } elseif ($thisSum < 0) {
            $thisSum = 0;
            $tempStart = $i + 1;
        }
    }
    return array($start, $end, $maxSum);
}

list($start, $end, $maxSum) = getMaxSum($arr);

echo "最大子序列是: ";
for ($i = $start; $i <= $end; $i++) {
    echo $arr[$i] . ' ';
}
echo "<br>最大子序列的和是 $maxSum";
// 輸出：最大子序列是: 4 -3 5 -2 -1 2 6  和為 11
?>

關鍵點總結

• 序列必須為整數。
• 若非全負數，最大子序列首項必為正數（負數開頭只會減小總和）。
• 全負數序列最大和為 0（空子序列）。
• 算法同樣適用於股票最大獲利（買賣一次）、最大子矩陣和等變體問題。