萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 實作最大子陣列和演算法:解決正負數陣列連續元素最大值問題

問題定義

給定一個包含正負整數的陣列,找出連續子陣列的最大和,並回傳該子陣列本身。這是經典的最大子陣列問題,也是 Kadane 演算法的典型應用場景。

核心演算法:Kadane's Algorithm

時間複雜度 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] 為例:

索引值curSummaxSum說明
0111新最大值,start=0, end=0
1-3-21歸負,重置 curSum=0, tempStart=2
2-5-51歸負,重置 curSum=0, tempStart=3
3-7-71歸負,重置 curSum=0, tempStart=4
4888新最大值,start=4, end=4
591717新最大值,end=5
6-11617未歸負,繼續累加
751117未超過最大值

最終最大子陣列為索引 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 與引用變數,程式碼簡潔且效能優異。記得處理全負數等邊界情況,並根據業務需求決定是否需要回傳所有最優解。

copyright © 萬盛學電腦網 all rights reserved