53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
Python solution 1:
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
curSum = maxSum = nums[0]
for num in nums[1:]:
curSum = max(num, curSum + num)
maxSum = max(curSum, maxSum)
return maxSum
分析：
在这种方法中，curSum既是指针又是结果的保存器：如果num之前的连续 k 项之和比 num 小，那么 curSum 充当指针，它会指向当前的 num；反之，它会存储包括 num 在内的连续 k+1 项之和：
curSum = max(num, curSum + num)
这一行代码之所以能够保证是连续的 k 项之和，就在于它起到了指针的作用：如果 curSum 移动了，那么求和子序列就会从 num 处重新开始累加，从而保证了子序列的连续性（不会跳过当前的数而去和后面的数相加）；如果指针没有移动，那么它会存储连续的 k+1 项之和。
curSum 的作用是负责遍历 nums 中所有可能的求和情况，它并不能保证在遍历完 nums 后 curSum 中存储的就是最大的子序和，因为在它找到最大子序和后，如果此时 nums 还没有遍历完，那它就要继续遍历 nums，从而有可能导致这个最大的子序和被别的数字代替。因此程序中又用到了 maxSum 这个存储器，其目的就是为了将 curSum 找到的那个最大的子序和保存下来。
Python solution 2:
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(1, len(nums)):
if nums[i-1] > 0:
nums[i] += nums[i-1]
return max(nums)
分析：
这个方法是基于这样一种思想：任给一个数字 m，假如我们想让这个数字变大，现在让它加上另外一个数 n，那么当 n 满足什么条件时 m 才会变大呢？显然，只有当 n 是一个正数的时候 m 才会变大。
现在假如给定一个序列 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，我们想要从中找到最大连续子序和，考虑从序列中的第一个元素开始，一个一个进行判断。判断的标准是这样的：
如果前面一个数为正数，那就让后面紧邻的那个数加上前面的这个数，并让二者之和替换掉后面紧邻的这个数；
否则，什么都不做。
按照这个原则，最终 nums 将变成：nums = [-2, 1, -2, 4, 3, 5, 6, 1, 5]，从而此时的 max(nums) 就是要找的最大连续子序和。