JdreamZhang ·分治算法之最大子數組問題
1. 前言
本節內容是分治算法系列之一：最大子數組問題，主要講解了什么是最大子數組問題，如何利用分治算法解決最大子數組問題，給出了最大子數組的實現偽代碼并進行分析，并用 java 語言進行了偽代碼實現，幫助大家通過最大子數組問題更好地理解分治算法思想的應用。
2. 什么是最大子數組問題？
最大子數組（Max Subarray）問題，是計算機科學與技術領域中一種常見的算法問題，主要可以利用分治思想進行快速實現。
最大子數組問題描述如下：假如我們有一個數組，數組中的元素有正數和負數，如何在數組中找到一段連續的子數組，使得子數組各個元素之和最大。
最大子數組問題在生活中有很多實際情況可以與其對應，比如說我們觀察某一股票在一段時間內的走勢，請問如何找出在哪一天買入，哪一天賣出可以賺到最大差價（這里假設你已經知道股票的價格走勢）？為了實現最大化的股票收益，我們需要考慮的是買進和賣出時候的價格變化幅度，因此從該股票的每日變化幅度來考慮這個問題更加合適。所以，我們可以將這個問題稍作變形：將股票價格走勢對應為每日股票價格漲跌，漲記為正值，跌記為負值，然后一段時間就對應一個正負數數組，并試圖找到該數組的最大子數組，就可以獲得最大收益。
接下來，就讓我們看看如何利用分治算法求解最大子數組問題吧。
3. 分治法求解最大子數組問題
在最大子數組問題之后，我們一起來看一下如何利用分治思想求解最大子數組問題。這里我們假設待初始的數組為 [12, -3, -16, 20, -19, -3, 18, 20, -7, 12, -9, 7, -10]，記為數組 A，并用 A [low,high] 表示這個數組，其中 low，high 是這個數組的最小最大下標， low = 0，high = A.length -1 , 然后我們需要找到該數組的其中某一個最大子數組。
Tips: 這里我們需要注意，同一數組的最大子數組可能有多個，所以我們在這里求解的時候只說求解某一個最大子數組。
3.1 分治算法求解思路
在這里，我們用分治算法求解最大子數組問題，主要思路如下：
-
步驟 1：
找到數組 A 的中間元素，其下標記為 mid，根據分治策略，將數組 A [low,high] 根據中間元素劃分為 A [low,mid]， A [mid+1,high] 兩個部分；
-
步驟 2：
假設數組 A 的最大子數組為 A [i, j]，那么 A [i, j] 只有以下三種可能：
a: 最大子數組 A [i, j] 完全位于 A [low, mid] 中，此時有 low <= i <= j <= mid;
b: 最大子數組 A [i, j] 完全位于 A [mid+1, high] 中，此時有 mid+1 <= i <= j <= high;
c: 最大子數組 A [i, j] 跨域了中間元素，則 low <= i <= mid <= j <= high。
分別計算上述三種對應的最大子數組的結果；
Tips: 在這里，情況 a 和情況 b 這兩種情況所得的子問題和之前求解數組 A 的最大子數組的問題形式完全一樣，這里是分治思想的主要體現，將大的問題拆分成了兩個相同形式的小問題；情況 c 這時候可以直接求解，在 3.2 節中會具體介紹其求解過程。
-
步驟 3
對步驟 2 三種情況的求解結果進行比較，其中最大子數組的結果為最大值的情況就是我們的所求結果。
3.2 求解思路詳解
首先，我們將 3.1 節中的求解思路用下圖表示：
如圖，我們可以更清楚地明白求解一個數組的最大子數組問題就是對 3.1 節中的步驟 2 中的三種情況的分別求解， 步驟 2 中的情況 a 和情況 b 可以通過遞歸求解得出結果，所以我們現在先看一下情況 c 的具體求解過程。情況 c 的求解很容易在線性時間內就可以得出結果，他并不是原問題的一個規模更小的實例，因為情況 c 中加入了一個限制（求出的子數組必須跨越下標為 mid 的中間節點）。如上圖的右邊圖形所示，情況 c 的求解結果都會有兩個子數組 A [i,mid] 和 A [mid+1,j] 組成，其中 low <= i <= mid <= j <=high。因此，我們只需要找出形如 A [i,mid] 和 A [mid+1,j] 的最大子數組，然后將其合并即可。
我們用下面的偽代碼 FindMaxCrossSubarray 描述 3.1 節中 步驟 2 中的情況 c 具體實現過程：
FindMaxCrossSubarray(A, low, mid ,high):
leftSum = minInteger; //設置左邊的最大連續和初始值為最小整數值
sum =0;
maxLeft = mid; //記錄左邊最大子數組的下標位置,初始化為mid
for (i=mid; i>=low; i--){
sum = sum + A[i];
if (sum > leftSum){
leftSum = sum;
maxtLeft = i;
}
}
rightSum = minInteger; //設置右邊的最大連續和初始值為最小整數值
sum = 0;
maxtRight = mid + 1; //記錄右邊最大子數組的下標位置,初始化為mid+1
for (j=mid+1; j<=low; j++){
sum = sum + A[j];
if (sum > rightSum){
rightSum = sum;
maxtRight = j;//記錄左邊最大子數組的下標位置
}
}
//返回結果是一個三元組數據，分別是最大子數組的開始下標，結束下標，求和的值
return (maxLeft,maxRight,leftSum+rightSum);
上述偽代碼的描述中的第 2 至第 11 行，是求解左半部分 A [low,mid] 的最大子數組的過程，因為必須包含下標為 mid 的元素，所以從下標為 mid 的中間節點開始逐步遞減到下標為 low 的元素，對應偽代碼中的第 5 至第 11 行的 for 循環結構，循環的過程中會記錄下左邊部分的最大子數組的具體值及左半部分的下標位置。同理，上述偽代碼的第 12 至第 21 行對應的是求解右半部分 A [mid+1,high] 的最大子數組的過程。最后，偽代碼中的第 23 行綜合左右兩邊求解結果，返回必須跨越下標為 mid 的中間元素時，對應的原數組 A 的最大子數組結果。
當我們可以清楚地知道步驟 2 中的情況 c 的求解過程時，我們就可以綜合知道對于數組 A 求解最大子數組的整體過程，用偽代碼 FindMaxSubarray 描述如下：
FindMaxSubarray(A,low,high):
if (high == low){
return new Result(low,high,A[low]); //基礎情況，只有一個元素時候的處理情況
}else {
//對應2.1節中步驟1，找到中間元素
int mid = (low + high)/2;
//對應2.1節中步驟2，分別對應a,b,c三種情況求解最大子數組結果
(leftLow,leftHigh,leftSum) = FindMaxSubarray(A,low,mid);
(rightLow,rightHigh,rightSum) = FindMaxSubarray(A,mid+1,high);
(crossLow,crossHigh,crossSum) = FindMaxCrossSubarray(A,low,mid,high);
//對應2.1節中步驟3，比較得出最后結果
if(leftSum >= righSum && leftSum >= crossSum){
return (leftLow,leftHigh,leftSum);
}else if (rightSum >= leftSum && rightSum >= crossSum){
return (rightLow,rightHigh,rightSum);
}else {
return (crossLow,crossHigh,crossSum);
}
}
上述求解數組 A 的最大子數組的整體過程偽代碼，主要就是由我們在 2.1 節中描述的三大步驟而來。代碼第 2 至第 4 行，主要表明了最基礎的情況的處理方式。代碼第 4 至第 18 行對應著具體的實現方式，第 8 行和第 9 行分別是對子問題的遞歸求解，第 10 行調用 FindMaxCrossSubarray 過程，求解跨越中間節點的最大子數組求解方式，最后第 12 至 18 行對比三種情況的結果得出最終結果。
4.JAVA 代碼實現
在說明求解最大子數組的整個過程之后，接下來，我們看看如何用 java 代碼實現最大子數組問題的求解。
package divide_and_conquer;
public class MaxSubarray {
//內部類，用來存儲最大子數組的返回結果，
private static class Result {
int low;
int high;
int sum;
public Result(int low, int high, int sum) {
this.low = low;
this.high = high;
this.sum = sum;
}
@Override
public String toString() {
return "Result{" +
"low=" + low +
", high=" + high +
", sum=" + sum +
'}';
}
}
private static Result FindMaxCrossSubarray(int[]A,int low, int mid, int high){
//尋找左邊的連續最大值及記錄位置
int leftSum = Integer.MIN_VALUE;
int sum = 0;
int maxLeft = mid;
for (int i=mid; i>=low; i--){
sum = sum + A[i];
if(sum > leftSum){
leftSum = sum;
maxLeft = i;
}
}
//尋找右邊的連續最大值及記錄位置
int rightSum = Integer.MIN_VALUE;
int maxRight = mid+1;
sum = 0;
for ( int j=mid+1; j<=high;j++){
sum = sum + A[j];
if(sum > rightSum){
rightSum = sum;
maxRight = j;
}
}
//返回跨越中間值的最大子數組結果
return new Result(maxLeft,maxRight,leftSum + rightSum);
}
public static Result FindMaxSubarray(int[] A, int low, int high){
//數組只有一個元素時的處理情況
if (high == low){
return new Result(low,high,A[low]);
}else {
//對應思路中步驟1，找到中間元素
int mid = (low + high)/2;
//對應思路中步驟2，分別對應a,b,c三種情況求解最大子數組結果
Result leftResult = FindMaxSubarray(A,low,mid);
Result rightResult = FindMaxSubarray(A,mid+1,high);
Result crossResult = FindMaxCrossSubarray(A,low,mid,high);
//對應步驟3，比較
if(leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum){
return leftResult;
}else if (rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum){
return rightResult;
}else {
return crossResult;
}
}
}
public static void main(String[] args){
int[] A = {12, -3, -16, 20, -19, -3, 18, 20, -7, 12, -9, 7, -10};
System.out.println(FindMaxSubarray(A,0,A.length-1).toString());
}
}
運行結果如下：
Result{low=6, high=9, sum=43}
運行結果中的 low 表示最大子數組在數組 A 中的開始下標，high 表示最大子數組在數組 A 中的終止下標，sum 表示最大子數組的求和值，對應到我們的實例數組 A 中，對應的最大最大子數組為 [18,20,-7,12]。
代碼中第 5 行至 25 行的 Result 內部類，主要是用來存儲最大子數組的返回結果，定義了子數組的開始下標，結束下標，求和值。代碼的第 27 至 55 行是最大子數組跨越中間節點時候的最大子數組求解過程。代碼的第 58 至 78 行是整個最大子數組的求解過程。代碼的第 81 行和 82 行是求解最大子數組過程的一個示例，輸出最大子數組的求解結果。
5. 小結
本節主要學習了利用分治思想求解最大子數組問題，學習本節課程需要熟悉分治算法的算法流程，知道分治算法在解決最大子數組時的實現思路，可以自己用代碼實現最大子數組問題的求解。在學習完本節課程之后，我們通過最大子數組這一實例介紹了分治算法的實際應用，幫助大家可以更好地理解分治算法。
2025 imooc.com All Rights Reserved |