這個題目需要使用到動態(tài)規(guī)劃敷扫，還不清楚什么是動態(tài)規(guī)劃的同學(xué)，可以看我的另一篇文章的解釋
題目
給定一個整數(shù)數(shù)組 nums 诚卸，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）葵第，返回其最大和。
示例
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大合溺，為 6卒密。
進(jìn)階:
如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解辫愉。
解法
初看這道題栅受，思路基本就是用遍歷的方法，就這個例子來說，一共有9個數(shù)字屏镊，我們把所有的排列組合列出來依疼，然后求出最大值。按照排列組合的數(shù)學(xué)算法而芥，一共有45個組合律罢，如果有n個數(shù)字，時間復(fù)雜度是棍丐，這樣的時間復(fù)雜度是明顯不能接受的误辑。
解法1 動態(tài)規(guī)劃
于是我們把目光落到動態(tài)規(guī)劃上面來，首先需要把這個問題分解成最優(yōu)子問題來解歌逢。最主要的思路就是將上面的45個組合進(jìn)行分類巾钉，分解成數(shù)量較少的幾個子問題。在這里我們一共有9個數(shù)字秘案，順理成章的我們把組合分解成9個小組的組合砰苍。
第一個子組合是以第一個數(shù)字結(jié)尾的連續(xù)序列，也就是
[-2]阱高，最大值-2第二個子組合是以第二個數(shù)字結(jié)尾的連續(xù)序列赚导，也就是
[-2,1], [1]，最大值1第三個子組合是以第三個數(shù)字結(jié)尾的連續(xù)序列赤惊，也就是
[-2,1,3], [1,3], [3]吼旧，最大值4以此類推。未舟。圈暗。
如果我們能夠得到每一個子組合的最優(yōu)解，也就是子序列的最大值处面，整體的最大值就可以通過比較這9個子組合的最大值來得到了〕е茫現(xiàn)在我們找到了最優(yōu)子問題，重疊子問題在哪呢魂角？那就得細(xì)心比較一下每個子問題昵济。
從第二個子組合和第三個子組合可以看到，組合3只是在組合2的基礎(chǔ)上每一個數(shù)組后面添加第3個數(shù)字野揪，也就是3访忿，然后增加一個只有第三個數(shù)字的數(shù)組[3]。這樣兩個組合之間的關(guān)系就出現(xiàn)了斯稳，可是我們不關(guān)心這個序列是怎么生成的海铆，只是關(guān)心最大值之間的關(guān)系。我們將子組合三分成兩種情況：
- 繼承子組合二得到的序列挣惰，也就是
[-2,1,3], [1,3]（最大值 = 第二個組合的最大值 + 第三個數(shù)字） - 單獨(dú)第三個數(shù)字的序列卧斟，也就是
[3]（最大值 = 第三個數(shù)字）
如果第二個序列的最大值大于0殴边，那么最大值1就比最大值2要大，反之最大值2較大珍语。這樣锤岸，我們就通過第二個組合的最大值和第三個數(shù)字，就得到了第三個組合的最大值板乙。因?yàn)榈诙€組合的結(jié)果被重復(fù)用到了是偷，所以符合這個重疊子問題的定義。通俗來講這個問題就變成了募逞，第i個子組合可以通過第i-1個子組合的最大值和第i個數(shù)字獲得蛋铆，如果第i-1個子組合的最大值沒法給第i個數(shù)字帶來正增益，我們就拋棄掉前面的子組合放接，自己就是最大的了刺啦。
來看看代碼，我們只需要一個變量subMax保存前面子組合的最大值透乾，另外一個max保存全局最大值洪燥。
public int maxSubArray(int[] nums) {
if (nums == null) {
return 0;
}
int max = nums[0]; // 全局最大值
int subMax = nums[0]; // 前一個子組合的最大值
for (int i = 1; i < nums.length; i++) {
if (subMax > 0) {
// 前一個子組合最大值大于0，正增益
subMax = subMax + nums[i];
} else {
// 前一個子組合最大值小于0乳乌，拋棄前面的結(jié)果
subMax = nums[i];
}
// 計算全局最大值
max = Math.max(max, subMax);
}
return max;
}
解法2 分治法
分治法是將整個數(shù)組切分成幾個小組，每個小組然后再切分成幾個更小的小組市咆，一直到不能繼續(xù)切分也就是只剩一個數(shù)字為止汉操。然后每個小組會計算出最優(yōu)值，匯報給上一級的小組蒙兰，一級一級匯報磷瘤，上級拿到下級的匯報找到最大值，得到最終的結(jié)果搜变。和合并排序的算法類似采缚，先切分，再合并結(jié)果挠他。
這個問題中的關(guān)鍵就是如何切分這些組合才能使每個小組之間不會有重復(fù)的組合（有重復(fù)的組合意味著有重復(fù)的計算量）扳抽，這個問題應(yīng)該困擾了不少的同學(xué)，我在學(xué)習(xí)理解的時候也花了不少時間殖侵。
首先是切分分組方法贸呢，就這個案例中的例子來，我們有一個數(shù)組[-2,1,-3,4,-1,2,1,-5,4]拢军，一共有9個元素楞陷，我們center=(start + end) / 2這個原則，得到中間元素的索引為4茉唉，也就是-1固蛾，拆分成三個組合：
-
[-2,1,-3,4,-1]以及它的子序列（在-1左邊的并且包含它的為一組） -
[2,1,-5,4]以及它的子序列（在-1右邊不包含它的為一組） - 任何包含
-1以及它右邊元素2的序列為一組（換言之就是包含左邊序列的最右邊元素以及右邊序列最左邊元素的序列结执，比如[4,-1,2,1]，這樣就保證這個組合里面的任何序列都不會和上面兩個重復(fù)）
以上的三個組合內(nèi)的序列沒有任何的重復(fù)的部分艾凯，而且一起構(gòu)成所有子序列的全集昌犹，計算出這個三個子集合的最大值，然后取其中的最大值览芳，就是這個問題的答案了斜姥。
然而前兩個子組合可以用遞歸來解決，一個函數(shù)就搞定沧竟，第三個跨中心的組合應(yīng)該怎么計算最大值呢铸敏？
答案就是先計算左邊序列里面的包含最右邊元素的的子序列的最大值，也就是從左邊序列的最右邊元素向左一個一個累加起來悟泵，找出累加過程中每次累加的最大值杈笔，就是左邊序列的最大值。同理找出右邊序列的最大值糕非，就得到了右邊子序列的最大值蒙具。左右兩邊的最大值相加，就是包含這兩個元素的子序列的最大值朽肥。
在計算過程中禁筏，累加和比較的過程是關(guān)鍵操作，一個長度為的數(shù)組在遞歸的每一層都會進(jìn)行
次操作衡招，分治法的遞歸層級在
級別篱昔，所以整體的時間復(fù)雜度是
，在時間效率上不如動態(tài)規(guī)劃的
復(fù)雜度始腾。
代碼如下
public int maxSubArray(int[] nums) {
return maxSubArrayDivideWithBorder(nums, 0, nums.length-1);
}
private int maxSubArrayDivideWithBorder(int[] nums, int start, int end) {
if (start == end) {
// 只有一個元素州刽，也就是遞歸的結(jié)束情況
return nums[start];
}
// 計算中間值
int center = (start + end) / 2;
int leftMax = maxSubArrayDivideWithBorder(nums, start, center); // 計算左側(cè)子序列最大值
int rightMax = maxSubArrayDivideWithBorder(nums, center + 1, end); // 計算右側(cè)子序列最大值
// 下面計算橫跨兩個子序列的最大值
// 計算包含左側(cè)子序列最后一個元素的子序列最大值
int leftCrossMax = Integer.MIN_VALUE; // 初始化一個值
int leftCrossSum = 0;
for (int i = center ; i >= start ; i --) {
leftCrossSum += nums[i];
leftCrossMax = Math.max(leftCrossSum, leftCrossMax);
}
// 計算包含右側(cè)子序列最后一個元素的子序列最大值
int rightCrossMax = nums[center+1];
int rightCrossSum = 0;
for (int i = center + 1; i <= end ; i ++) {
rightCrossSum += nums[i];
rightCrossMax = Math.max(rightCrossSum, rightCrossMax);
}
// 計算跨中心的子序列的最大值
int crossMax = leftCrossMax + rightCrossMax;
// 比較三者，返回最大值
return Math.max(crossMax, Math.max(leftMax, rightMax));
}
解法3 Kadane算法
Kadane全名叫Joseph "Jay" Born Kadane浪箭，是卡耐基梅隆大學(xué)的統(tǒng)計學(xué)方面的教授穗椅，于1984年提出提出了線性解決這個問題的辦法。
國內(nèi)網(wǎng)上有很多材料提到了Kadane算法奶栖，并且將Kadane算法和動態(tài)規(guī)劃并列到了一起匹表，表明是兩個不同的算法，但是當(dāng)搜索外文網(wǎng)站的時候驼抹，大家用的Kadane算法和動態(tài)規(guī)劃的思路是一模一樣的桑孩，參考我的第一個參考文章，這里貼一下Wikipedia的代碼框冀，感覺和我們的動態(tài)規(guī)劃的算法似乎不太一樣
def max_subarray(numbers):
"""Find a contiguous subarray with the largest sum."""
best_sum = 0 # or: float('-inf')
current_sum = 0
for x in numbers:
current_sum = max(0, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum
我們把這個代碼放到網(wǎng)站跑一邊流椒，發(fā)現(xiàn)沒有通過，因?yàn)楫?dāng)這個數(shù)組全是負(fù)數(shù)的時候明也，它的結(jié)果是0宣虾，改進(jìn)方法是把max(0, current_sum + x)換成max(x, current_sum + x)惯裕，這樣就沒有問題了：
def max_subarray(numbers):
"""Find a contiguous subarray with the largest sum."""
best_sum = 0 # or: float('-inf')
current_sum = 0
for x in numbers:
current_sum = max(x, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum
現(xiàn)在大家有沒有感覺這段代碼很眼熟，沒錯绣硝！這就是我們的動態(tài)規(guī)劃的解法蜻势。和原來的一樣，核心思路都是判斷以前一個元素結(jié)尾的子序列的最大值能不能給當(dāng)前元素結(jié)尾的序列提供增益鹉胖。當(dāng)初布朗大學(xué)的Ulf Grenander教授在1977年提出這個問題的時候是為了展示數(shù)字圖像中一個簡單的最大似然估計模型握玛，可能沒有過多考慮道負(fù)數(shù)的問題，所以后來在解決的時候就沒有考慮到全是負(fù)數(shù)的情況甫菠。
延伸——獲取最大序列的起始和結(jié)束位置
可以使用我們的第一種方法也就是動態(tài)規(guī)劃的方法來找到這個位置挠铲，將以這個元素結(jié)尾的的最大子序列的位置找出來，然后每次比較最大值的時候更新一下最大值的位置就行了
public int maxSubArrayPosition(int[] nums) {
if (nums == null) {
return 0;
}
int start = 0;
int end = 0;
int subStart = 0;
int subEnd = 0;
int max = nums[0]; // 全局最大值
int subMax = nums[0]; // 前一個子組合的最大值
for (int i = 1; i < nums.length; i++) {
if (subMax > 0) {
// 前一個子組合最大值大于0寂诱，正增益拂苹，更新最后元素位置
subMax = subMax + nums[i];
subEnd++;
} else {
// 前一個子組合最大值小于0，拋棄前面的結(jié)果痰洒，更新當(dāng)前最大值位置
subMax = nums[i];
subStart = i;
subEnd = i;
}
// 計算全局最大值瓢棒，更新位置，將全局最優(yōu)解的位置更新
if (subMax > max) {
max = subMax;
start = subStart;
end = subEnd;
}
}
System.out.println("[" + start + ","+ end +"]");
return max;
}
參考
Kadane’s Algorithm Explained
Maximum subarray problem
求最大連續(xù)子序列的和丘喻，兩種解法：動態(tài)規(guī)劃 & Kadane算法
分治策略結(jié)合遞歸思想求最大子序列和
Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?
更多內(nèi)容請看我的個人博客
