leetcode 53 python 最大子序和

传送门

题目要求

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

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

思路一

设默认最大子序和max是第一个元素，从索引为０开始，记录元素的连续累加和sum，如果sum>max，　令max = sum；如果出现sum < 0的情况（此时再连续累加下个元素无论其为正或负，都会导致连续累加和小于元素本身），将sum重新置为０。

→_→ talk is cheap, show me the code

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max = nums[0]
        sum = 0
        for i in nums:
            sum += i
            if sum > max:
                max = sum
            if sum < 0:
                sum = 0
        return max