給定一個包含正負整數的陣列,找出連續子陣列的最大和,並回傳該子陣列本身。這是經典的最大子陣列問題,也是 Kadane 演算法的典型應用場景。
時間複雜度 O(n),空間複雜度 O(1),單次遍歷即可求解:
<?php
function maxSubarray(array $list): array {
$curSum = 0; // 目前子陣列累加和
$maxSum = 0; // 歷史最大和
$start = 0; // 最大子陣列起始索引
$end = 0; // 最大子陣列結束索引
$tempStart = 0; // 暫存起始索引
foreach ($list as $i => $val) {
$curSum += $val;
// 當前累加和超過歷史最大值,更新記錄
if ($curSum > $maxSum) {
$maxSum = $curSum;
$start = $tempStart;
$end = $i;
}
// 累加和歸負,拋棄前序,從下一個元素重新開始
if ($curSum < 0) {
$curSum = 0;
$tempStart = $i + 1;
}
}
// 邊界情況:全負數陣列時,最大值為 0(空子陣列),需特別處理
if ($maxSum === 0) {
$maxVal = max($list);
$idx = array_search($maxVal, $list);
return ['max_sum' => $maxVal, 'subarray' => [$maxVal], 'start' => $idx, 'end' => $idx];
}
$subarray = array_slice($list, $start, $end - $start + 1);
return ['max_sum' => $maxSum, 'subarray' => $subarray, 'start' => $start, 'end' => $end];
}
// 測試
$list = [1, -3, -5, -7, 8, 9, -11, 5];
$result = maxSubarray($list);
echo "最大和: {$result['max_sum']}\n"; // 17
echo "子陣列: " . implode(', ', $result['subarray']) . "\n"; // 8, 9
以陣列 [1, -3, -5, -7, 8, 9, -11, 5] 為例:
| 索引 | 值 | curSum | maxSum | 說明 |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 新最大值,start=0, end=0 |
| 1 | -3 | -2 | 1 | 歸負,重置 curSum=0, tempStart=2 |
| 2 | -5 | -5 | 1 | 歸負,重置 curSum=0, tempStart=3 |
| 3 | -7 | -7 | 1 | 歸負,重置 curSum=0, tempStart=4 |
| 4 | 8 | 8 | 8 | 新最大值,start=4, end=4 |
| 5 | 9 | 17 | 17 | 新最大值,end=5 |
| 6 | -11 | 6 | 17 | 未歸負,繼續累加 |
| 7 | 5 | 11 | 17 | 未超過最大值 |
最終最大子陣列為索引 4-5 的 [8, 9],和為 17。
原演算法會回傳 0(空子陣列),但實務上通常期望「至少選一個元素」。修正如上方程式碼所示:檢測 $maxSum === 0 時,改回傳最大單一元素。
輸入 [] 時拋出例外或回傳空結果,視業務需求定。
若有多個子陣列和相同且為最大值,需記錄所有區間:
function maxSubarraysAll(array $list): array {
$curSum = 0;
$maxSum = PHP_INT_MIN;
$results = [];
$tempStart = 0;
foreach ($list as $i => $val) {
$curSum += $val;
if ($curSum > $maxSum) {
$maxSum = $curSum;
$results = [[$tempStart, $i]];
} elseif ($curSum === $maxSum) {
$results[] = [$tempStart, $i];
}
if ($curSum < 0) {
$curSum = 0;
$tempStart = $i + 1;
}
}
return ['max_sum' => $maxSum, 'ranges' => $results];
}
| 方法 | 時間複雜度 | 空間複雜度 | 適用場景 |
|---|---|---|---|
| 暴力雙層迴圈 | O(n²) | O(1) | 教學示意、極小資料 |
| 分治法 | O(n log n) | O(log n) | 學術研究、平行運算 |
| Kadane 演算法 | O(n) | O(1) | 生產環境、大規模資料 |
Kadane 演算法以優雅的單次遍歷解決最大子陣列問題,是每位開發者必備的演算法工具箱。PHP 實作時善用 foreach 與引用變數,程式碼簡潔且效能優異。記得處理全負數等邊界情況,並根據業務需求決定是否需要回傳所有最優解。