清大資工程式設計 1

資訊

程式碼範例都是由 Python 撰寫的。

演算法

最大子數列問題（Maximum Subarray Problem）

假設一個數列為 [-2, -3, 4, -1, -2, 1, 5, -3]，它的最大子數列和是 7，因為 $4 + (-1) + (-2) + 1 + 5 = 7$ 。

如果我們使用暴力法，就必須嘗試所有的連續子數列組合。一個長度為 $n$ 的陣列，會有 $n(n+1)/2$ 個子數列，時間複雜度為 $O(n^2)$。因此，我們需要一個更有效率的演算法來快速求出最大子數列的和。

Kadane's algorithm

Kadane 的想法非常直覺，只需要使用兩個變數並遍歷數列一次。

• cur_sum：當前正在追蹤的子數列總和
• max_sum：遇過的最大子數列總和

每讀到一個新數字時，就決定要「延續目前的子數列」，還是「從這個數字重新開始」。換句話說，如果 cur_sum + n[i] 比 n[i] 還要大的話，就要延續目前的子數列；如果n[i] 比 cur_sum + n[i] 還要大的話，代表重新開始會獲得更大的值。

這樣就能在一次掃描中完成計算，時間複雜度會優化成 $O(n)$。

def max_subarray_kadane(numbers):
    best_sum = float('-inf') # 負無限小
    current_sum = 0
    
    for x in numbers:
        current_sum = max(x, current_sum + x)
        best_sum = max(best_sum, current_sum)
        
    return best_sum

前綴和（Prefix sum）

除了 Kadane 的演算法之外，我們也可以透過前綴和的想法來求出最大子數列和。

假設原始數列為 $n$，我們定義他的前綴和數列 $p$ 為：

$$p[i] = n[0] + n[1] + ... + n[i]$$

那麼任意子數列區間 [l, r] 的總和，就可以用前綴差表示為：

$$n[l] + n[l+1] + ... + n[r] = p[r] - p[l-1]$$

為了求出最大的子數列和，我們會希望 $p[r]$ 盡可能大、並且 $p[l-1]$ 盡可能小。我們會需要三個變數：

• prefix：當前前綴和
• min_prefix：最小的前綴和（$p[l-1]$ 要盡可能小）
• best：遇過的最大子數列總和

每讀到一個新數字，就更新 prefix，並且以這個位置為 r 計算子數列和 prefix - min_prefix，並且跟 best 比較，若更大則更新。最後，也更新 min_prefix 確保他是最小的前綴和 p[l-1]。

這樣一樣能在一次掃描中完成計算，時間複雜度會優化成 $O(n)$。

def max_subarray_prefix(numbers):
    best = float('-inf')
    prefix = 0
    min_prefix = 0  # 最小前綴和

    for x in numbers:
        prefix += x
        best = max(best, prefix - min_prefix)
        min_prefix = min(min_prefix, prefix)

    return best