给定一个整数数组，找到一个具有最大和的连续子数组 (子数组最少包含一个数)，返回其最大和。
例如，给定数组 [-2,1,-3,4,-1,2,1,-5,4]，
连续子数组 [4,-1,2,1] 的和最大，为 6。
"""
遍历数组，当从头到尾部遍历数组遇到一个数有两种选择:
key point:
（1）加上这个数后数值变大：继续加后面的数，最大值为当前相加后的值
（2）加上这个数后数值变小：从当前开始重新加后面的数，最大值为当前最大值
"""
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
sum = 0
max_sum = nums[0]
for i in range(len(nums)):
sum = max(sum + nums[i], nums[i])
max_sum = max(sum, max_sum)
return max_sum
网友评论