蠻力法、分治法和動態規劃法求解最大子數組問題的思考

陳 艷，文曉棠

（廣州華商學院數據科學學院，廣州 510520）

0 引言

最大子數組問題是一個眾所周知的算法問題，在計算機科學、金融和工程等各個領域都有許多實際應用。這個問題涉及到在一維數字數組中找到具有最大和的連續子數組。有幾種方法可以解決這個問題，包括蠻力算法、分治算法和動態規劃算法［1］。在本文中，對這些方法進行了比較，并提供了實驗結果來分析它們的性能。本研究的目標是確定解決最大子數組問題的最有效方法，并全面了解用于解決該問題的不同算法。

1 問題概述

假如我們有一個數組，數組中的元素有正數和負數，如何在數組中找到一段連續的子數組，使得子數組各個元素之和最大。

定義：數組中連續的一段序列稱為子數組。

定義：數組中元素和最大的非空子數組稱為最大子數組。詳細定義為：

輸入：給定一個數組X［1，2，…，n］，對于任意數組下標為l，r（l≤r）的非空子數組，其和記為S（l，r）

輸出：求S（l，r）的最大值，記為Smax。

比如已知序列X=（-2，2，5，-7，-1，2，-4，3），求序列的最大子數組，正確的答案為X［2，3］，子數組和為7。本文將以此序列為例全面分析各種不同算法解決此問題。

2 蠻力算法

蠻力算法也稱為窮舉法或暴力法，它是算法設計中最常見的方法之一。蠻力算法的基本思路是對問題的所有可能狀態一一測試，直到找到解或將全部可能狀態都測試為止。蠻力法是一種簡單、直接地解決問題的方法，通常直接基于問題的描述和所涉及的概念定義來解決問題。蠻力算法是基于計算機運算速度快這一特性，在解決問題時采用的一種“懶惰”策略。蠻力算法是學習算法的基礎，很多算法的優化都是在蠻力算法的基礎上進行的，因此想要熟練應用各種算法策略，培養算法思維，必須對蠻力算法有深刻的認識和熟練的應用。

蠻力算法是解決最大子數組問題的一種簡單方法。它包括生成所有可能的子數組并計算它們的和。然后，返回具有最大和的子數組。已知序列如圖1所示。

圖1 序列X

圖2 求S3的思路

遍歷子數組X［l，2，…，r］的下標，l的取值范圍：1～n，r的取值范圍：l～n，遍歷過程中對子數組元素求和，并記錄最大值Smax。

算法偽代碼如下：

該算法的時間復雜度為O（n3），因為它需要生成n2個子數組并計算它們的和。

3 優化的蠻力算法

根據上述算法，當求S（i,j）時，通過來得到，求S（i，j+1）時，通過來得到，通過觀察發現，S（i，j+1）的求解包含著子問題S（i,j）的求解，如果能利用S（i,j）的解來求解S（i，j+1），則能改進算法的效率。以此為優化的目標，設計優化的蠻力算法如下：

通過上述改進，減少了一層循環的應用，算法的復雜度由O（n3）降為O（n2），效率提高了一個數量級。

4 分治法

分治算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同［2］，求出子問題的解，通過合并的方式就可得到原問題的解。用分治法求解的問題具有如下基本特征：①該問題的規模縮小到一定的程度就可以容易地解決；②該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；③利用該問題分解出的子問題的解可以合并為該問題的解；④該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

分治法求解問題的基本步驟分為三步［3-4］：

第一步：分解原問題。將原問題分解為兩個或多個與原問題性質相同、規模更小的子問題，不同的問題分解的策略不一樣，比如二路歸并排序的分解策略是一分為二，快速排序的分解策略為利用數組劃分算法實現分解。

第二步：求解子問題。對子問題的求解分別調用一次遞歸即可，因為子問題本質上和原問題性質相同，只是規模變小而已。

第三步：合并子問題的解。通過對子問題的解進行合并，可以得到原問題的解。此步反映了分治法具有最優子結構的性質，即原問題的解可以通過子問題的解組合得到。不同的是，對子問題的解合并方式不一樣，比如歸并算法需要有專門的合并算法來實現，而快速排序卻沒有嚴格意義上的合并過程。

分治算法是解決最大子數組問題的一種有效方法。該算法遞歸地將輸入數組分為兩半，得到兩個子問題，分別解決每個子問題的最大子數組問題，再求出跨左右兩個子問題的最大子數組，然后將解組合起來，由此得到原始數組的最大子數組。按照分治法解決問題的基本步驟具體設計思想如下：

（1）分解

將數組X［1，2，…，n］分為和從中間分成兩半，得到兩個子問題，即求解數組的最大子數組問題和求解數組的最大子數組問題。

（2）求解

遞歸求解上述兩個子問題，將結果分別記為S1，S2。

（3）合并

兩個子問題的解S1，S2可能是原問題的解，也可能不是原問題的解，因為還存在一個跨左右兩個子數組的最大子數組，記為S3。S3有個特點，它一定是包含左邊子問題的最后一個元素和右邊子問題的第一個元素，即跨中間點的最大子數組。不難理解，原問題的解在S1，S2和S3中，為Smax=max｛S1,S2,S3｝。顯然關鍵問題是求S3。

對于S3的求解，可以用蠻力法，但效率低，達到O（n2）的規模。設左邊子問題的最后一個元素下標為m，則右邊子問題第一個元素下標為m+1，如果分別求解出左邊以元素X［m］結尾的最大子數組，記為left；求出右邊以元素X［m+1］開始的最大子數組，記為right，則可順利求出S3=left+right。見圖。

以此為思路，設計求S3的算法getS3（X，low，mid，high），偽代碼如下：

算法中，求left的復雜度為O（mid），求right的復雜度為O（n-mid），則求S3的算法復雜度為O（n），顯然比直接蠻力法求S3的效率要高一個數量級。

分治法求解最大子數組問題的主算法Max-SubArray（X，low，high）偽代碼如下：

5 動態規劃法

動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，然后從這些子問題的解得到原問題的解［3］。與分治法不同的是，適合于用動態規劃求解的問題，經分解得到的子問題往往不是相互獨立的。也就是各個子問題包含公共的子子問題［4］。為了解決子問題重復計算的問題，動態規劃算法對每個子問題只計算一次，不管該子問題是否以后被用到，都將其結果保存到一張表中，從而避免每次遇到各個子問題時重新計算答案［5］。動態規劃通常應用于求解最優解問題，如0-1背包問題，最大子數組問題，矩陣鏈乘法問題等。

動態規劃法所能解決的問題一般具有以下幾個特征：①大問題可分解性。該問題可以分解為若干個規模較小的問題，即該問題具有最優子結構性質；②子問題易解決性。該問題的規模縮小到一定的程度就可以容易地解決；③解可合并性。利用該問題分解出的子問題的解可以組合為該問題的解；④子問題重疊性。當計算出某個子問題的解時，后續多個問題都需要計算該子問題的解，所以計算出某個子問題的解，并將其保存，就節省了分治法重復計算的時間。

動態規劃算法求解問題的基本步驟分為四步：

第一步：問題結構分析。分析問題的特點，結合問題的特點分析問題的結構，找到合適的辦法來表示問題，進而通過此表示方法來表示原問題。

第二步：遞推關系的建立。動態規劃算法的核心是填表，表中每個單元格代表一個子問題的解，每個單元格的解是通過其他子問題的解組合得到的，即動態規劃算法也要滿足最優子結構的性質。因此要分析子問題之間的依賴關系，也即分析最優子結構性質，由此得到子問題求解過程的組合方式，即遞推關系。

第三步：確定計算順序。對于填表的辦法，不同的問題填法不一樣，有的表從左向右自上而下來填，有的表需要從后往前填，有的甚至按對角線的方式從左向右填，具體的填表方式因問題性質而異，需要通過第二步得到的子問題間的遞推關系來確定。

第四步：最優方案的追蹤。通過第三步得到了問題的最優值，對應的最優方案可以通過記錄填表時的決策過程，通過回溯的方式來得到。

動態規劃算法是解決最大子數組問題的另一種有效方法。該算法以數組中的每一個元素作為一個子數組的最后一個元素，向前遍歷求和。通過規律觀察發現，如果此元素的前一個子數組和為負，則以這個元素為最后一個元素的子數組的最大和為此元素本身；如果此元素之前的子數組和為正，則以這個元素為最后一個元素的子數組最大和為此元素本身加上前一個最大子數組和。每做一次子數組求和，就與前面出現的最大和作比較，如果此子數組大于前面的最大子數組，就將其賦值給最大值。若定義D［i］表示以X［i］結尾的最大的子數組和，則D［i］的求解如圖3所示。

圖3 求解D［i］的思路

按照此思路，根據動態規劃算法求解問題的基本步驟，設計如下：

問題結構分析：

定義D［i］：表示以X［i］結尾的最大的子數組和，則原問題表示為Smax=max｛D［i］｝（1≤i≤n）。

遞推關系建立：

根據遞推關系的分析，D［i］實際上是一張一維表，故將原問題轉換為填D這張表的問題，如圖4所示。

圖4 表D的結構

計算順序：

根據遞推式，將兩個子問題D［i］和D［i-1］在表中的位置關系表示出來，如圖5所示，通過觀察發現要求D［i］，需要先求D［i-1］，則得到此表的計算順序為從左到右的順序，原問題的解在表中的某個位置。如圖6所示。

圖5 D［i］和D［i-1］在表中的位置關系

圖6 計算順序

以此為思想，設計算法MaxSubjectarrayDP（X，n）偽代碼如下：

該算法用一層循環實現，時間復雜度為O（n），因為它在輸入數組中迭代一次，在恒定時間內解決每個子問題。

6 算法對比實驗

按上述設計實現這三種算法，并進行對比測試。首先生成一些隨機數數組，數組規模從100 到100000000 不等。然后對每個數組運行優化的蠻力算法、分治算法和動態規劃算法，并計算它們所需的時間。測試結果見表1。

表1 實驗數據

實驗結果表明，對于較大的輸入大小，動態規劃算法優于蠻力算法和分治算法。例如，對于大小為100000 的輸入數組，蠻力算法需要1 s 以上的時間來計算最大子數組，分治法需要1 ms，動態規劃法需要3 ms，此時，動態規劃法無優勢；但數組規模到1000000，蠻力法已經不是秒級，程序運行時幾分鐘之內未出結果，分治法18 s，動態規劃只需1 ms；數組規模到10000000 時，動態規劃法的優勢更明顯，且隨著數組規模的增大，動態規劃的優勢不斷增大。由此可見，分治算法比蠻力算法表現更好，但對于較大的輸入大小，仍然比動態編程算法花費更長的時間。

7 結語

本文比較了解決最大子數組問題的不同方法，包括蠻力算法、分治算法和動態規劃算法。實驗結果表明，動態規劃算法是解決這個問題的最有效方法，特別是對于大輸入量的情況。分治算法也是一個很好的替代方案，但它不如動態規劃算法有效。蠻力算法是一種基本的方法，只能應用于較小的輸入大小。總體而言，動態規劃算法為最大子數組問題提供了最優解，其時間復雜度為O（n）。