53.最大子序和问题

Last modified date

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

Kadane算法

  • 算法描述:
    • 遍历该数组, 在遍历过程中, 将遍历到的元素依次累加起来, 当累加结果小于或等于0时, 从下一个元素开始,重新开始累加。
    • 累加过程中, 要用一个变量(max_so_far)记录所获得过的最大值
    • 一次遍历之后, 变量 max_so_far 中存储的即为最大子片段的和值。
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sum = 0
        max_so_far = nums[0]
        for num in nums:
            sum += num
            if sum > max_so_far:
                max_so_far = sum
            if sum < 0:
                sum = 0
        return max_so_far

该问题最初由布朗大学的Ulf Grenander教授于1977年提出,不久之后卡内基梅隆大学的Jay Kadane提出了该问题的线性算法。

https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E5%88%97%E9%97%AE%E9%A2%98

真卡蛋。

发表评论