最大连续子序列号

题外话：这是前几年写的一篇文章，在知乎专栏和慕课网发表过，现在搬到自己的公众号来，作为算法专栏的第一篇文章～

最近看到的一道编程题目：

有一个数组，如1， －5， 8， 3， －4， 15， －8，查找其中连续和最大的相邻串的值。在本例中，最大值为8 ＋ 3 ＋ －4 ＋ 15 ＝ 22.

这道题最容易想到的算法就是暴力搜索：

1. 第一遍从数组第一个元素开始，找到它与后面每个元素之间的连续元素之和的最大值并记录下来；
2. 第二遍从数组第二个元素开始，找到它与后面每个元素之间的连续元素之和的最大值，并与前一遍找到的最大值做比较，记录二者之中较大的值；
3. 以此类推直到最后一个元素，便可以找到整个数组的最大连续子序列和。

下面看看go代码：

package main

import (
        "fmt"
)

func maxSumOfSubArray(a []int) int {
        // 初始化最大和为数组的第一个元素
        maxSum := a[0]
  
        n := len(a)

        // 第 i 遍搜索从第 i 个元素开始往后搜索
        for i := 0; i < n; i++ {
                // sum用于记录从第 i 个元素到第 k 个元素的和，i <= k
                sum := 0

                for k := i; k < n; k++ {
                        sum += a[k]
                        if sum > maxSum {
                                //找到一个比之前找到的最大值更大的连续子序列和
                                maxSum = sum
                        }
                }
        }
   
        return maxSum
}

func main()  {
        a := []int{1, -5, 8, 3, -4, 15, -8}
        fmt.Println("max sum is:", maxSumOfSubArray(a))
}

这个算法简单粗暴易于理解，但效率不高，要找到最大连续子序列和一共需要n + (n - 1) + (n - 2) + ... + 1次访问数组元素，也就是时间复杂度是O(n*n)。那么有没有更好的算法呢？

我们来分析一下。

首先假设我们已经找到了最大连续和子串在数组中的起始位置（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，－2， 3， 4，5，很容易发现－2这个元素满足前述的第2个和第3个性质：

• -2 本身是负数
• -2 + 1 = -1 < 0

所以-2是这样一个分界点，最大和的字串要么在－2之后要么在之前，－2之前的和是1，之后的和sum = 3 + 4 + 5 = 12，所以这个字串的最大和为12。

我们稍微改变一下数组的元素就可以看到最大和字串在分解点之前的情况：

第二个例子：假设数组为 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]))。

那么怎么去找这个分界点呢？

我们从前面的第3个性质可以看出如果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.

分析到这里算法基本上就出来了，下面给出go代码：

func maxSumOfSubArray(a []int) int {
        maxSum := a[0]
        sum := a[0]

        for i := 1; i < len(a); i++ {
                   sum += a[i]
                   if sum < 0 { // 分界点，重新求和
                           sum = 0
                   } else {
                           if sum > maxSum {
                                   maxSum = sum // 记录最大和
                           }
                   }
        }

        return maxSum
}