题目：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
求最大字段和。
给出一个数列。输出这个数列的最大字段和。比如：[−2,1,−3,4,−1,2,1,−5,4]，最大子段和是[4,-1,2,1]，输出是6.
题目思路：
通常求最大字段和有四种方法：
1.动态规划；时间复杂度为O（n）
2. 将给定的序列分成长度相等的两段，分别求出这两段的最大字段和；时间复杂度为O（n*logn）
3.先计算字段和结果，存储到s[]数组中，即预处理，这样在每次计算a[i]到a[j]之间的数和的时候就等于s[j]-s[i]；时间复杂度变为O（n^2）
4.枚举i和j，求i和a[i]到a[j]之间的和的最大值；时间复杂度O（n^3）
这题用动态规划的思想：b[i] = max{b[i - 1] + a[i],a[i]}
代码：
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ size = len(nums) if size == 0: return sum = nums[0] d = 0 # 设置临时变量，与sum对比，大于0有效，小于0不更新 for i in range(size): if d > 0: d += nums[i] else: d = nums[i] if d > sum: # 更新sum值 sum = d return sum if __name__ == "__main__": s = Solution() print(s.maxSubArray(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))