Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
给定整数数组nums，找到具有最大总和的子数组（数组要求连续）并且返回数组的和，给定的数组包含至少一个数字。
- 我们用res来表示最终的和，用temp来表示临时的和
- 初始时res = nums[0]，temp = 0
- 遇到一个值，我们就把它加到temp上面，如果temp大于res，把temp赋值给res
- 如果temp小于res但是大于0，继续加和
- 如果temp小于零，我把temp置为零，因为此时temp已经小于零了，如果保留temp当前的值再往里面加值，整个的和一定会变得更小[因为temp当前是负数]，
- 也就是说当temp是负数时，temp的贡献一定是负，无论后面加什么值，一定会使得当前的子数组和更小
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 初始化为nums[0]
res = nums[0]
temp = 0
for item in nums:
# 往temp加和
temp += item
# 如果比res大，更新res
if temp > res:
res = temp
# 如果小于0，则重置为0
if temp < 0:
temp = 0
return res