53. 最大子序和

【Description】

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

示例:

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

【Idea】
①贪心
借用两个int变量tpSum和maxSum存储。
从左向右遍历该数组。每当右移一位，将tpSum与当前元素大小比较，如果大于当前元素，则tpSum更新值，并拿更新后的tpSum继续向前求和比较。若和小于当前元素，表明局部最优解已结束。更新maxSum=max(tpSum,maxSum)，更新tpSum=nums[i]
tips：这个题我是在动态规划里刷到的。但是贪心求解的话与动态规划有些矛盾的地方，分类私以为有些不妥。

【Solution】

# ①贪心求解
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        length = len(nums)
        if length == 1:
            return nums[0]
        maxSum = nums[0]
        i = 1
        tp = nums[0]
        while i < length:
            if nums[i] >= nums[i] + tp:
                tp = nums[i]
            else:
                tp = nums[i] + tp
            maxSum = max(tp, maxSum)
            # print(i, tp, maxSum)
            i += 1
        return maxSum

image.png