[toc]
难度：easy
题目
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路
最大和的连续子数组：这个概念误导了我一下，我还以为是说子数组是连续增长的。
但正确的理解应该是：
每个数相加。每次下一个数加上去，数组的总和增大，如果加上去减小了那么久不符合最大和的要求，就清空重新加
题解
解法1：动态规划
def maxSubArray(self, nums):
for i in range(1, len(nums)): # 因为下面用了 i-1, 所以从 i 从 1 开始
pre_max = max(nums[i-1], 0) # 其实这里是正负数判断：若为正数，加上去肯定总和会变大；为负数，加上去总和会减小，不符合最大和。所以总和归零重新来
nums[i] = nums[i] + pre_max # 把原数组替换掉了 这里的 nums[i] 就是下一次循环的 nums[i-1]
return max(nums)
