leetcode 53.最大子序和 python实现

题目要求

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

示例:

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

解题思路

从头开始遍历，以坐标 i 为结束点的最大子序和为f (i) ,则以坐标 i+1 为结束点的最大子序和 f(i+1) 为：

if f(i) < 0:
	f(i+1) = nums[i+1]
else:
	f(i+1) = f(i) + nums[i+1]

得出来的f(i+1)和原来的max作比较。
Answer:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_num = nums[0]
        last = nums[0]
        for i in range(1, len(nums)):
            last = last+nums[i] if last >= 0 else nums[i]
            max_num = max(max_num, last)
        return max_num

补充：
找到了更为清晰明了的写法：

class Solution:
    def maxSubArray(self, nums):  
 
        """ 
        :type nums: List[int] 
        :rtype: int 
        """  
        le = len(nums)
        for i in range (1,le):
            ###前i-1个最大的结果已经存在i-1中，每次都可看做是两个数相加
            submax = max(num[i]+num[i-1],nums[i])
            ###把每次最大的结果赋值给当前值，然后继续下一个两数相加
            nums[i] = submax
        return max(nums)