描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1]
输出：1示例 3：
输入：nums = [0]
输出：0示例 4：
输入：nums = [-1]
输出：-1链接
https://leetcode-cn.com/problems/maximum-subarray/
思路
直接的思路是动态： $f(i)$ 代表以第$$i$$个数结尾的「连续子数组的最大和」
$$
f(i)=max\{f(i−1)+nums[i],nums[i]\}
$$
这个需要空间复杂度$O(n)$
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = [0] * len(nums)
max_v = nums[0]
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1]+ nums[i], nums[i])
if dp[i] > max_v:
max_v = dp[i]
return max_v改进方法：依据动态的思想：每个数字遍历的时候，当前结尾的sum值依据前一个值是否大于0，然后更新最大值。初始最大sum为num第0个元素。
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_sum = nums[0]
cur_sum = 0
for num in nums:
if cur_sum > 0:
cur_sum += num
else:
cur_sum = num
max_sum = max(cur_sum, max_sum)
return max_sum
