最大連續子序列和（演算法）

版權聲明：本文為原創文章，禁止任何形式及除知乎之外的媒體的轉載。

最近看到的一道編程題目：

有一個數組，如1， －5， 8， 3， －4， 15， －8，查找其中連續和最大的相鄰串的

很多人拿到這個題目的第一反應就是很簡單啊，動態規劃思想很容易搞定，但也有同學像我一樣第一次看到這個題目時覺得很難，但我們不要被困難嚇倒，先分析看看能不能有啥思路。

首先假設我們已經找到了最大連續和子串在數組中的起始位置（i）和結束位置（j），其中i <= j，即最大和maxSum = a[i] + a[i + 1] + ... + a[j]，我們來看看這個子串有什麼性質：

1，a[i] > 0，否則我們完全可以去掉a[i]這個元素 而得到一個更大的和；

2, i > 0且a[i - 1] < 0 或 i == 0，下面假設i > 0，這一條性質也是因為如果a[i - 1] > 0的話我們求和時可以加上a[i - 1]這個元素得到一個更大的和；

3, 元素a[i - 1]與它之前的任一元素之間的子串之和sum < 0 ，即對於任何一個m(0 <= m < i - 1)，則有a[m] + a[m + 1] + ... + a[i - 1] < 0，這條性質同樣可以用反證法證明。

如果一下想不明白上面的第三條性質，可以在紙上用筆畫畫圖看看。根據第二三條性質，我們感覺 a[i - 1]是一個分界點，最大和的子串要麼就在a[i - 1]元素之後，要麼就在a[i - 1]之前，最大和的子串不可能跨過a[i - 1]這個點。仔細用筆畫畫圖想一下為什麼，還是用前面的反證來思考。下面舉2個例子來看看：

1，假設數組為 1，－2， 3， 4，5，很容易發現－2這個元素滿足前述的第二個和第三個性質：

-2 本身是負數；

-2 + 1 = -1 < 0

所以-2是這樣一個分界點，最大和的字串要麼在－2之後要麼在之前，－2之前的和是1，之後的和sum = 3 + 4 + 5 = 12，所以這個字串的最大和為12；

我們稍微改變一下數組的元素就可以看到最大和字串在分解點之前的情況：

2，假設數組為 100，－101， 3， 4，5，很容易發現－101這個元素滿足前述的第二個和第三個性質：

-101 本身是負數；

-101 + 100 = -1 < 0

所以-101是這樣一個分界點，最大和的字串要麼在－101之後要麼在之前，－101之前的和是100，之後的和sum = 3 + 4 + 5 = 12，所以這個字串的最大和為100；

根據前面的分析我們可以得出結論：

只要找到分解點 a[i - 1]，最大和的子串要麼就在a[i - 1]元素之後，要麼就在a[i - 1]

之前，最大和的子串不可能跨過a[i - 1]這個點；一個數組中可能有多個這種分界點，

但每個分界點都可以把前後完全分開，可以單獨算分界點之間的最大和，然後在這些最

大和之間取最大值

假設對於數組a，我們找到了兩個分界點a[i]和a[j],那麼整個數組的最大字串和max(sum(a[0]...a[i-1]), sum(a[i+1]...a[j-1]), sum(a[j+1]...a[len-1]))

那麼怎麼去找這個分界點呢？我們從前面的第三個性質可以看出如果a[i-1]是分界點，那麼a[0]到a[i - 1]之和必定為負數，所以我們就從a[0]開始逐個往後求和，為了便於描述我們把這個和記為sum，sum第一次變成負數時就是我們要找的分界點。可能您會說sum(a[0]...a[i-1])<0並不代表sum(a[m]...a[i-1])<0 (m < i -1)呀？看看找這個分界點的方法，我們是從第一個元素開始求和，分界點是當sum第一次變成負數時找到的元素，也就是說a[0]到a[m-1]之和必定大於0，記為sum1, a[m]到a[i-1]之和記為sum2, 於是有關係sum1 + sum2 = sum < 0 推出sum2 ＝ sum - sum1 < 0.

分析到這裡演算法基本上就出來了，下面給出python代碼：

#!/usr/local/bin/python3.5 def calculateMaxSumOfSubArray(arr): sum = 0 maxSum = 0 for i in arr: sum += i if sum < 0: #分界點，重新求和 sum = 0 else: if sum > maxSum: maxSum = sum #記錄最大和 return maxSum #測試if __name__ == "__main__": arr = [1, -5, 8, 3, -4, 15, -8] print("max sum is:", calculateMaxSumOfSubArray(arr))

推薦閱讀：