手撕LeetCode #53——Python

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解题思路：
如果前面的和为负数，就开启新的子数组。因为加上一个负数，只会让和更小。

for i in range(1, len(nums)):
  if nums[i-1] > 0:
    nums[i] += nums[i-1]
return max(nums)

时间复杂度：O(N)
空间复杂度：O(N)