2.6 最大子序列和
题目描述（第53题）
求数组中最大连续子序列和，例如，给定数组A=[1,3,-2,4,-5]，则最大连续子序列和为6，即1+3+（-2）+4=6。
首先明确一下题意。
● 题目说的子数组是连续的。
● 题目只需要求和，不需要返回子数组的具体位置。
● 数组中的元素是整数，可能是正数、负数和0。
● 子序列的最小长度为1。
比如：
● 对于数组[1,-2,3,5,-3,2]，应该返回3+5=8。
● 对于数组[0,-2,3,5,-1,2]，应该返回3+5+(-1)+2=9。
● 对于数组[-9,-2,-3,-5,-3]，应该返回-2。
解法一 暴力法（超时）
一般情况下，可以先用暴力法进行分析，再一步步进行优化。
思路
首先来试一下最直接的方法，就是计算所有的子序列和，然后取出最大值。定义 Sum[i,…,j]为数组A中第i个元素到第j个元素的和，其中0≤i≤j < n，遍历所有可能的Sum[i,…,j]即可。
代码
复杂度分析
● 时间复杂度：O(n2)，其中n为数组长度。
● 空间复杂度：O(1)。
解法二 分治法
解法一的空间复杂度非常理想，但是时间复杂度有点高，该怎么优化呢？
思路
这道题实际上是一个可以用多种方法解决的题目，如果你想到了上面的解法，我想面试官肯定不会满意，而如果你一时想不到更好的解决方法的话，有两种方法可以帮助你厘清思路。
1.举几个简单的例子。这种方法通常适用于很复杂的问题，人们一时间难以发现其中的规律。树和链表等题目使用这种方法比较好，搭配画图来将问题进行可视化的展现效果会更好。
2.将大问题拆解为若干子问题，通过解决子问题，以及探寻子问题和大问题之间的关系来解决。
这里我们采用第2种方法。
假如先把数组平均分成左、右两部分，那么此时有3种情况。
● 最大子序列全部在数组左部分，不妨用left表示。
● 最大子序列全部在数组右部分，不妨用right表示。
● 最大子序列横跨数组左右部分，不妨用crossMaxSum表示。
对于前两种情况，相当于将原问题转化成了规模更小的同类问题。对于第3种情况，由于已知循环的起点（即中点），只需要向左、向右分别找出左边和右边的最大子序列，那么当前最大子序列就是向左能够达到的最大子序列+nums[mid]+向右能够达到的最大子序列。因此，一个思路就是每次都将数组分成左、右两部分，然后分别计算上面这3种情况的最大子序列和，最后返回最大值即可。
代码
复杂度分析
● 时间复杂度：从上图可以看出每层的节点在[n,2n]之间，且一共有 logn层，因此时间复杂度为O(nlogn)，其中n为数组长度。
● 空间复杂度：空间复杂度取决于函数调用栈的深度，故空间复杂度为O(logn)，其中n为数组长度，这也可以从上图直观地感受到。
解法三 动态规划
思路
我们重新思考一下这个问题，观察能否将其拆解为规模更小的问题，并找出递推关系来解决？
不妨假设问题Q(list,i)表示list中以索引i结尾的最大子序列和，那么原问题就转化为Q(list,i)中的最大值，其中i =0,1,2,…,n-1。
继续来看一下Q(list,i)和Q(list,i-1)的关系，即如何根据Q(list,i-1)推导出Q(list,i)。
1.如果Q(list,i-1)>0，则表示以索引i-1结尾的最大子序列和大于0，因此nums[i]一定要和Q(list,i-1)部分结合，这样才能使结果更优，即Q(list,i)=Q(list, i-1)＋nums[i]，这是一种贪心的思想。
2.如果Q(list,i-1)≤0，则为了使结果更优，nums[i]应该不与Q(list,i-1)相加。
分析到这里，递推关系就很明朗了，即Q(list,i)=max(0,Q(list,i-1))+nums[i]。
代码
复杂度分析
● 时间复杂度：O(n)，其中n为数组长度。
● 空间复杂度：O(1)。
解法四 前缀和
思路
下面从数学分析的角度来看一下这个题目。定义函数S(i)，它的功能是计算从0（包括0）开始加到i（包括i）的值，即S(i)=list[0]+list[1]+…+list[i]。那么S(j)-S(i-1)就等于从i开始（包括i）加到j（包括j）的值，这在数学上被称为前缀和求差，因此实际上只需要遍历一次计算出所有的S(i)，其中i等于0,1,2,…,n-1，然后利用前缀和就可以计算出任意区间的和。这种算法的时间复杂度为O(n)，空间复杂度为O(1)。
其实很多题目都有这样的思想，比如每日一题——电梯问题（见参考链接/正文[1]）。甚至可以将此方法扩展到二维空间，即对二维空间计算前缀和，利用前缀和的技巧计算任意矩阵区域的和，由于篇幅原因，这里就不展开讲解了。
代码
复杂度分析
● 时间复杂度：O(n)，其中n为数组长度。
● 空间复杂度：O(1)。
小结
我们使用了4种方法来解决最大子序列和问题，并详细分析了各个解法的思路及复杂度。即使你无法通过数学方法解决，通过分治法或动态规划解决也是可以的。相信下次你碰到相同或类似的问题时也能够发散思维，做到一题多解、多题一解。
这里只是求出了最大的和，如果题目进一步要求求出最大子序列和的子序列呢？如果题目允许不连续呢？又该如何思考和变通？如果将数组改成二维的，求解最大矩阵和该怎么计算？这些问题就留给读者自己思考了。