最大子数组和

很自然的想到使用前缀和，使用一个变量记录目前为止的最小前缀和，遍历数组时，计算以目前为尾部的最大子数组和，并和最大值进行比较，比较容易犯错的地方就是各个值的初始化和循环内的三段代码的先后。

class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ n=len(nums) min_sum=0 s=0 answer=float('-inf') for i in range(n): s+=nums[i] answer=max(answer,s-min_sum) min_sum=min(min_sum,s) return answer

使用分治的思路：

分治法的第一步永远是极其粗暴的：从正中间一刀劈开，分成左半边和右半边。

要找的那个“和最大的连续子数组”，它的藏身之处只有可能有三种情况：

1. 纯左派：它完完全全缩在左半边里。

2. 纯右派：它完完全全缩在右半边里。

3. 骑墙派：它跨越了中间那条切分线，一部分在左边，一部分在右边。

• 唯一需要亲自动手解决的，就是算出骑墙派的最大值，然后把这三个值拿出来比大小，最大的那个就是整个数组的最终答案

计算骑墙派的最大值

既然它跨越了中间线，那它一定包含中间线左边紧挨着的元素，和右边紧挨着的元素。

所以只需要：

1. 从中间线向左，一路加过去，记录下向左能延伸出的最大和。

2. 从中间线向右，一路加过去，记录下向右能延伸出的最大和。

3. 把这俩最大和拼在一起，就是横跨中间的最大连续子数组和