最大子數列問題

在計算機科學中，最大子數列問題（英語：Maximum subarray problem）的目標是在數列的一維方向找到一個連續的子數列，使該子數列的和最大。例如，對一個數列[−2, 1, −3, 4, −1, 2, 1, −5, 4]，其連續子數列中和最大的是[4, −1, 2, 1], 其和為6。

該問題最初由布朗大學的烏爾夫·格雷南德（英語：Ulf Grenander）教授於1977年提出，當初他為了展示數字圖像中一個簡單的最大似然估計模型。不久之後卡內基梅隆大學的傑·卡丹（英語：Joseph Born Kadane）提出了該問題的線性算法。(Bentley 1984)。

卡丹算法

卡丹算法掃描一次整個數列的所有數值，在每一個掃描點計算以該點數值為結束點的子數列的最大和（正數和）。該子數列由兩部分組成：以前一個位置為結束點的最大子數列、該位置的數值。因為該算法用到了「最佳子結構」（以每個位置為終點的最大子數列都是基於其前一位置的最大子數列計算得出），該算法可看成動態規劃的一個例子。

算法可用如下Python代碼實現：

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

該問題的一個變種是：如果數列中含有負數元素，允許返回長度為零的子數列。該問題可用如下代碼解決：

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

這種算法稍作修改就可以記錄最大子數列的起始位置。卡丹算法時間複雜度為 ${\mathcal {O}}(n)$ ，空間複雜度為 ${\mathcal {O}}(1)$ 。

引用

Bentley, Jon, Programming pearls: algorithm design techniques, Communications of the ACM, 1984, 27 (9): 865–873, doi:10.1145/358234.381162 .
Brodal, Gerth Stølting; Jørgensen, Allan Grønlund, A linear time algorithm for the k maximal sums problem, Mathematical Foundations of Computer Science 2007, Lecture Notes in Computer Science 4708, Springer-Verlag: 442–453, 2007, doi:10.1007/978-3-540-74456-6_40 .
Takaoka, T., Efficient algorithms for the maximum subarray problem by distance matrix multiplication (PDF), Electronic Notes in Theoretical Computer Science, 2002, 61 [2014-10-02], （原始內容 (PDF)存檔於2013-10-29） .

外部連結