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

今天給大家?guī)硪坏罉O其經(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ù)組和不超過6.

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

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

暴力求解

這種解法最簡(jiǎn)單，我們把所有子數(shù)組找出來，然后依次計(jì)算其和，找出一個(gè)最大的出來，比如給定數(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è)賮砜匆幌逻@個(gè)過程，這里的問題在于計(jì)算每個(gè)子數(shù)組的和時(shí)有很多重復(fù)計(jì)算，比如我們知道了子數(shù)組[1,2]的和后再計(jì)算數(shù)組[1,2,3]的值時(shí)完全可以利用子數(shù)組[1,2]的計(jì)算結(jié)果而無需從頭到尾再算一遍，也就是說我們可以利用上一步的計(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)，比第一種解法高了很多。

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

答案是肯定的。

分而治之

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

然后呢？

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

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

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

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

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

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

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

根據(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è)問題還有另一種更妙的解決方法，我們令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è)最大的就好了，依賴子問題解決當(dāng)前問題的解就是所謂的動(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ì)懷疑這段代碼的正確性，但它的確是沒有任何問題的，而且這段代碼的時(shí)間復(fù)雜度只有O(N)，這段代碼既簡(jiǎn)單運(yùn)行速度又快，這大概就是算法的魅力吧。