Leetcode剑指-Offer-42-连续子数组的最大和-Python实现同53题

• 题目要求：

• 思路：

  • 维护一个 tmp，用来保存临时的最大值
  • 维护一个 res，用来保存全局最大值，也就是结果
  • 遍历数组，如果当前的 tmp 小于 0，那么把当前的值赋给 tmp，如果当前的值大于 0，把当前的值加上 tmp 的值的和赋给 tmp
  • 把 res 和 tmp 最大的那个赋给 res
  • 循环结束，返回 res
• 核心代码：

# res 的初始值为数组当中的随机一个元素即可，初始不能为 0，因为有可能数组中所有的元素都小于 0
res = nums[-1]
tmp = 0
for i in nums:
    if tmp < 0:
        tmp = i
    else:
        tmp += i
    res = max(res, tmp)
return res

• 完整代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[-1]
        tmp = 0
        for i in nums:
            if tmp < 0:
                tmp = i
            else:
                tmp += i
            res = max(res, tmp)
        return res