最近看到的一道编程题目：
有一个数组，如1， －5， 8， 3， －4， 15， －8，查找其中连续和最大的相邻串的值。在本例中，最大值为8 ＋ 3 ＋ －4 ＋ 15 ＝ 22.
很多人拿到这个题目的第一反应就是很简单啊，动态规划思想很容易搞定，但也有同学像我一样第一次看到这个题目时觉得很难，但我们不要被问题吓倒，先分析看看能不能有啥思路。
首先假设我们已经找到了最大连续和子串在数组中的起始位置（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))
网友评论