文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書
本文主要是對最大子數(shù)組（序列）問題求解的學(xué)習(xí)與總結(jié)，最大子數(shù)組問題是一道經(jīng)典的算法題，這道題解法有很多突雪，因此可以學(xué)習(xí)到很多求解問題的思路，并可以學(xué)習(xí)到算法的優(yōu)化過程帚戳。
1. 問題描述
英文：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
中文：
主要是給定一個數(shù)組棵帽，求解數(shù)組的子數(shù)組中，數(shù)組元素和最大的那一個子數(shù)組旺矾，返回的是最大子數(shù)組的和蔑鹦。
2. 求解
解法一
最簡單也是最容易想到的思路就是三層循環(huán)，對(i,j),i<=j的情況進(jìn)行遍歷箕宙，這種情況下的算法復(fù)雜度為O($n^3$)嚎朽。代碼如下：
public class Solution {
public int maxSubArray(int[] nums) {
//如果需要節(jié)省空間，可將n替換
int n = nums.length;
int max = nums[0];
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++){
int sum = 0;
//注意k的邊界扒吁，存在i=j的情況
for(int k = i; k <= j; k++) {
sum += nums[k];
if(sum > max) {
max = sum;
}
}
}
}
return max;
}
}
Leetcode上的運行結(jié)果如下：
解法二
從Leetcode結(jié)果可以看出火鼻，時間超時了，O($n3$)的時間復(fù)雜度確實太高了雕崩，需要進(jìn)行優(yōu)化魁索。分析上面的代碼，在i不變的情況下盼铁，j每增加1粗蔚，其和都是在上次求和基礎(chǔ)上加上最新的元素，而在第三層循環(huán)中都是重新從i開始計算求和饶火，因此存在數(shù)據(jù)冗余（求和的重復(fù)計算）鹏控，因此需要需要去掉算法中的冗余部分。這種情況下的代碼復(fù)雜度變?yōu)镺($n2$)肤寝，代碼如下：
public class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int max = nums[0];
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = i; j < n; j++){
sum += nums[j];
if(sum > max) {
max = sum;
}
}
}
return max;
}
}
Leetcode上運行結(jié)果如下：
解法三
從Leetcode結(jié)果可以看出当辐，時間還是超時了，但從執(zhí)行的測試數(shù)據(jù)數(shù)量上來看鲤看，比第一次多執(zhí)行了兩個缘揪，但在最后一個測試數(shù)據(jù)上時間超時了。那么能不能有進(jìn)一步的優(yōu)化呢义桂？答案是肯定有的找筝。可以使用分治法來求解慷吊，算法復(fù)雜度為O(nlogn)袖裕，但是其實本題并不適合使用分治法，太復(fù)雜溉瓶。雖然算法復(fù)雜度降低了一些急鳄，因此這里略過分治法谤民，直接尋找更優(yōu)解法。
解法四
還有沒有更好的方法呢攒岛？答案也是肯定的赖临。首先假設(shè)存在最大子數(shù)組X，則最大子數(shù)組X中的任意一個子數(shù)組x都不應(yīng)該為負(fù)數(shù)灾锯，如果x為負(fù)數(shù)兢榨，則X必定不是最大子數(shù)組（可用反證法證明）。根據(jù)這個思想顺饮，我們只需要以此累加數(shù)組元素吵聪，并將和與0比較，如果小于0兼雄，則需要在剩下的元素中重新尋找是否存在最大子數(shù)組吟逝，如果不小于0，則與保存的最大子數(shù)組值進(jìn)行比較赦肋，如果大于最大子數(shù)組值块攒，則更新最大子數(shù)組值。這樣只需要一次遍歷就能找到最大子數(shù)組佃乘，這種解法的算法復(fù)雜度為O(n)囱井。根據(jù)這個思路，解決這個問題的算法復(fù)雜度代碼如下：
public class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int max = nums[0];
int sum = 0;
for(int i = 0; i < n; i++) {
sum += nums[i];
if(sum > max) {
max = sum;
}
if(sum < 0) {
sum = 0;
}
}
return max;
}
}
Leetcode通過了趣避。
解法五
還有沒有別的方法呢庞呕？答案還是肯定的。使用動態(tài)規(guī)劃求解程帕。動態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)住练，又隨即引起狀態(tài)的轉(zhuǎn)移。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的愁拭，所以讲逛，這種多階段最優(yōu)化決策解決問題的過程就稱為動態(tài)規(guī)劃。 使用動態(tài)規(guī)劃求解問題岭埠，最重要的就是確定動態(tài)規(guī)劃三要素：（1）問題的階段妆绞；（2）每個階段的狀態(tài)；（3）從前一個階段轉(zhuǎn)化到后一個階段之間的遞推關(guān)系枫攀。
1.起始階段(i=0)，max = nums[0]株茶；2.第i(i > 0)個階段来涨，max = curMax[i]，curMax是第i個階段的最大子序列和启盛；3.第i-1和第i個階段的關(guān)系蹦掐，curMax[i] = Math.max(curMax[i - 1] + nums[i], nums[i])技羔；4.根據(jù)前面動態(tài)規(guī)劃的定義，則最大子序列和max = Math.max(max, curMax[i])卧抗。
public class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
//curMax是當(dāng)前的最大子序列和
int[] curMax = new int[n];
curMax[0] = nums[0];
int max = nums[0];
for (int i = 1; i < n; i ++) {
curMax[i] = Math.max(curMax[i - 1] + nums[i], nums[i]);
max = Math.max(max, curMax[i]);
}
return max;
}
}
Leetcode通過了藤滥。
分析解法四與解法五
其實解法四與解法五是一致的，解法四中的sum等于解法五中的curMax[i]社裆，解法五中如果curMax[i-1]小于0拙绊，則curMax[i] = nums[i]，而在解法四中由于第i-1次時sum=curMax[i-1]泳秀，因此需要將sum重置為0标沪，則sum + nums[i] = nums[i]，與curMax[i] = nums[i]是一致的嗜傅。如果解法五中curMax[i-1]大于等于0金句，則curMax[i] = curMax[i - 1] + nums[i]，此時方法四中sum = sum + nums[i]吕嘀。而第i-1次時违寞，sum = curMax[i - 1]，兩者也是等價的偶房。解法五中的curMax[0]替換為sum趁曼，curMax[i]替換為sum，將curMax[i] = Math.max(curMax[i - 1] + nums[i], nums[i]);變換為sum += nums[i];和if(sum < 0) { sum = 0; }蝴悉，即可將代碼從解法五變換為解法四的代碼彰阴。
