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