鐵子們，我是小風(fēng)哥，你也可以叫我島主

今天給大家?guī)?lái)一道極其經(jīng)典的題目，叫做最大和子數(shù)組，給定一個(gè)數(shù)組，找到其中的一個(gè)連續(xù)子數(shù)組，其和最大。

示例：

輸入:nums=[-2,1,-3,4,-1,2,1,-5,4]
輸出:6
解釋:子數(shù)組[4,-1,2,1]的和為6，其它任何連續(xù)的子數(shù)組和不超過(guò)6.

想一想該怎樣解決這個(gè)問(wèn)題。

如果你一時(shí)想不到解法可以從暴利解法開始。

暴力求解

這種解法最簡(jiǎn)單，我們把所有子數(shù)組找出來(lái)，然后依次計(jì)算其和，找出一個(gè)最大的出來(lái)，比如給定數(shù)組[1,2,3]，那么我們能找出子數(shù)組：[1]，[2]，[3]，[1,2]，[2,3]，[1,2,3]，很顯然這里和最大的子數(shù)組為[1,2,3]，其值為6。

intsum(vector&nums,intb,inte){
intres=0;
for(;b<=?e;?b++)?{
????????res?+=?nums[b];
????}
????returnres;
}
intmaxSubArray(vector&nums){
intsize=nums.size();
intres=0x80000000;
for(inti=0;ifor(intj=i;jreturnres;
}

這種解法最簡(jiǎn)單，該算法的時(shí)間復(fù)雜度為O(n^3)，其中找出所有子數(shù)組的時(shí)間復(fù)雜度為O(n^2)，計(jì)算每個(gè)子數(shù)組的和的時(shí)間復(fù)雜度為O(n)，因此其時(shí)間復(fù)雜度為O(n^3)。

讓我們?cè)賮?lái)看一下這個(gè)過(guò)程，這里的問(wèn)題在于計(jì)算每個(gè)子數(shù)組的和時(shí)有很多重復(fù)計(jì)算，比如我們知道了子數(shù)組[1,2]的和后再計(jì)算數(shù)組[1,2,3]的值時(shí)完全可以利用子數(shù)組[1,2]的計(jì)算結(jié)果而無(wú)需從頭到尾再算一遍，也就是說(shuō)我們可以利用上一步的計(jì)算結(jié)果，這本身就是動(dòng)態(tài)規(guī)劃的思想。

基于該思想我們可以對(duì)上述代碼簡(jiǎn)單改造一下：

intmaxSubArray(vector&nums){
intsize=nums.size();
intres=0x80000000;
for(inti=0;ifor(intj=i+1;jreturnres;
}

看到了吧，代碼不但更簡(jiǎn)潔，而且運(yùn)行速度更快，該算法的時(shí)間復(fù)雜度為O(n^2)，比第一種解法高了很多。

還有沒(méi)有進(jìn)一步提高的空間呢？

答案是肯定的。

分而治之

我們?cè)谥暗奈恼轮姓f(shuō)過(guò)，分治也是一種非常強(qiáng)大的思想，具體應(yīng)該這里的話我們可以把整個(gè)數(shù)組一分為二，然后子數(shù)組也一分為二，不斷劃分下去就像這樣：

然后呢？

然后問(wèn)題才真正開始有趣起來(lái)，注意，當(dāng)我們劃分到最下層的時(shí)候，也就是不可再劃分時(shí)會(huì)得到兩個(gè)數(shù)組元素，比如對(duì)于數(shù)組[1,2]會(huì)劃分出[1]與[2]，此時(shí)[1]與[2]不可再劃分，那么對(duì)于子問(wèn)題[1,2]，其最大子數(shù)組的和為max(1+2, 1,2)，也就是說(shuō)要么是左半部分的元素值、要么是右半部分的元素值、要么是兩個(gè)元素的和，就這樣我們得到了最后兩層的答案：

假設(shè)對(duì)于數(shù)組[1,2,3,4]，一次劃分后得到了[1,2]與[3,4]，用上面的方法我們可以分別知道這兩個(gè)問(wèn)題的最大子數(shù)組和，我們?cè)鯓永蒙鲜龅拇鸢竵?lái)解決更大的問(wèn)題，也就是[1,2,3,4]呢？

很顯然，對(duì)于[1,2,3,4]來(lái)說(shuō)，最大子數(shù)組的和要么來(lái)自左半部分、要么來(lái)自右半部分、要么來(lái)自中間部分——也就是包含2和3，其中左半部分和右半部分的答案我們有了，那么中間部分的最大和該是多少呢？

其實(shí)這個(gè)問(wèn)題很簡(jiǎn)單，我們從中間開始往兩邊不斷累加，然后記下這個(gè)過(guò)程的最大值，比如對(duì)于[1,-2,3,-4,5]，我們從中間的3開始先往左邊累加和是:{1+(-2)+3, (-2)+3, 3}也就是{2,1,3}，因此我們以中間數(shù)字為結(jié)尾的最大子數(shù)組和為3：

另一邊也是同樣的道理，只不過(guò)這次是以中間數(shù)字為起點(diǎn)向右累加：

然后這三種情況中取一個(gè)最大值即可，這樣我們就基于子問(wèn)題解決了更大的問(wèn)題：

此后的道理一樣，最終我們得到了整個(gè)問(wèn)題的解。

根據(jù)上面的分析就可以寫代碼了：

intgetMaxSum(vector&nums,intb,inte){
if(b==e)returnnums[b];
if(b==e-1)returnmax(nums[b],max(nums[e],nums[b]+nums[e]));
intm=(b+e)/2;
intmaxleft=nums[m];
intmaxright=nums[m];
intsum=nums[m];

for(inti=m+1;i<=?e;?i++)?{
????????sum?+=?nums[i];
????????maxright?=?max(maxright,?sum);
????}

????sum?=?nums[m];
????for(inti=m-1;i>=b;i--){
sum+=nums[i];
maxleft=max(maxleft,sum);
}
returnmax(getMaxSum(nums,b,m-1),max(getMaxSum(nums,m+1,e),maxleft+maxright-nums[m]));
}
intmaxSubArray(vector&nums){
returngetMaxSum(nums,0,nums.size()-1);
}

上述這段代碼的時(shí)間復(fù)雜度為O(NlogN)比第二種方法又提高了很多。

動(dòng)態(tài)規(guī)劃

實(shí)際上這個(gè)問(wèn)題還有另一種更妙的解決方法，我們令dp(i)表示以元素A[i]為結(jié)尾的最大子數(shù)組的和，那么根據(jù)這一定義則有：

這是很顯然的，注意dp(i)的定義，是以元素A[i]為結(jié)尾的最大子數(shù)組的和，因此dp(i)的值要么就是A[i]連接上之前的一個(gè)子數(shù)組，那么不鏈接任何數(shù)組，那么最終的結(jié)果一定是以某個(gè)元素為結(jié)尾的子數(shù)組，因此我們從所有的dp(i)中取一個(gè)最大的就好了，依賴子問(wèn)題解決當(dāng)前問(wèn)題的解就是所謂的動(dòng)態(tài)規(guī)劃。

有了這些分析，代碼非常簡(jiǎn)單：

intmaxSubArray(vector&nums){
intsize=nums.size();
vectordp(size,0);
intres=dp[0]=nums[0];
for(inti=1;ireturnres;
}

這段代碼簡(jiǎn)單到讓人難以置信，只有8行代碼，你甚至可能會(huì)懷疑這段代碼的正確性，但它的確是沒(méi)有任何問(wèn)題的，而且這段代碼的時(shí)間復(fù)雜度只有O(N)，這段代碼既簡(jiǎn)單運(yùn)行速度又快，這大概就是算法的魅力吧。