本文首發(fā)自「慕課網(wǎng)」，想了解更多IT干貨內(nèi)容，程序員圈內(nèi)熱聞，歡迎關(guān)注！

作者| 慕課網(wǎng)精英講師 JdreamZhang

最大子數(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ù)組問題吧。

1. 分治法求解最大子數(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ù)組。

1.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é)果。

1.2 求解思路詳解

首先，我們將 3.1 節(jié)中的求解思路用下圖表示：

如圖，我們可以更清楚地明白求解一個(gè)數(shù)組的最大子數(shù)組問題就是對(duì) 1.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描述 1.1 節(jié)中步驟 2中的情況 c 具體實(shí)現(xiàn)過程：

FindMaxCrossSubarray(A,low, mid ,high):leftSum=minInteger; //設(shè)置左邊的最大連續(xù)和初始值為最小整數(shù)值sum=0;maxLeft=mid; //記錄左邊最大子數(shù)組的下標(biāo)位置,初始化為midfor(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+1for(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);代碼塊1234567891011121314151617181920212223

上述偽代碼的描述中的第 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){returnnew 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); }elseif(rightSum >= leftSum && rightSum >= crossSum){return(rightLow,rightHigh,rightSum); }else{return(crossLow,crossHigh,crossSum); } } 代碼塊12345678910111213141516171819

上述求解數(shù)組 A 的最大子數(shù)組的整體過程偽代碼，主要就是由我們?cè)?1.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é)果。

2.JAVA 代碼實(shí)現(xiàn)

在說明求解最大子數(shù)組的整個(gè)過程之后，接下來，我們看看如何用 java 代碼實(shí)現(xiàn)最大子數(shù)組問題的求解。

packagedivide_and_conquer;publicclassMaxSubarray{//內(nèi)部類，用來存儲(chǔ)最大子數(shù)組的返回結(jié)果，privatestaticclassResult{intlow;inthigh;intsum;publicResult(intlow,inthigh,intsum){this.low = low;this.high = high;this.sum = sum; }@OverridepublicStringtoString(){return"Result{"+"low="+ low +", high="+ high +", sum="+ sum +}; } }privatestaticResultFindMaxCrossSubarray(int[]A,intlow,intmid,inthigh){//尋找左邊的連續(xù)最大值及記錄位置intleftSum = Integer.MIN_VALUE;intsum =0;intmaxLeft = mid;for(inti=mid; i>=low; i--){ sum = sum + A[i];if(sum > leftSum){ leftSum = sum; maxLeft = i; } }//尋找右邊的連續(xù)最大值及記錄位置intrightSum = Integer.MIN_VALUE;intmaxRight = mid+1; sum =0;for(intj=mid+1; j<=high;j++){ sum = sum + A[j];if(sum > rightSum){ rightSum = sum; maxRight = j; } }//返回跨越中間值的最大子數(shù)組結(jié)果returnnewResult(maxLeft,maxRight,leftSum + rightSum); }publicstaticResultFindMaxSubarray(int[] A,intlow,inthigh){//數(shù)組只有一個(gè)元素時(shí)的處理情況if(high == low){returnnewResult(low,high,A[low]); }else{//對(duì)應(yīng)思路中步驟1，找到中間元素intmid = (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){returnleftResult; }elseif(rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum){returnrightResult; }else{returncrossResult; } } }publicstaticvoidmain(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()); } } 代碼塊123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384

運(yùn)行結(jié)果如下：

Result{low=6, high=9, sum=43} 代碼塊1

運(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é)果。

3. 小結(jié)

本篇文章主要利用分治思想求解最大子數(shù)組問題，需要大家充分熟悉了解分治算法的算法流程，知道分治算法在解決最大子數(shù)組時(shí)的實(shí)現(xiàn)思路，可以自己用代碼實(shí)現(xiàn)最大子數(shù)組問題的求解。這次我們通過最大子數(shù)組這一實(shí)例介紹了分治算法的實(shí)際應(yīng)用，希望可以幫助大家更好地理解分治算法。

歡迎關(guān)注「慕課網(wǎng)」，發(fā)現(xiàn)更多IT圈優(yōu)質(zhì)內(nèi)容，分享干貨知識(shí)，幫助你成為更好的程序員！