相@

ss

firefly

滇西 2021-12-10

null

alg

dp@kadane

# kadane算法 On经典子数组和
# 用局部最优来更新全局最优
def kadane(nums):
    # 全局/局部
    ans = local = nums[0]
    for x in nums[1:]:
        # 局部最优，当前元素结尾的最大子数组和
        local = max(x, local + x)  # 要么接着加，要么从当前重新开始
        # 全局最优
        ans = max(ans, local) 
    return ans

return kadane(nums)

kadane是dp的一种特殊情况