[英雄星球七月集训LeetCode解题日报] 第28日 动态规划

日报

• 今天的题目是最大子段和，也叫最大子数组，经典的kadane算法，在图形领域是常用算法。
• 同时，这也是我的入坑题，领略到算法之美的题。从这题开始，我发现我自己脑子是不够的，有了套路可以秒杀！
• 该问题最初由布朗大学的Ulf Grenander教授于1977年提出，当初他为了展示数字图像中一个简单的最大似然估计模型。不久之后卡内基梅隆大学的Jay Kadane提出了该问题的线性算法。

题目

一、 53. 最大子数组和

链接: 53. 最大子数组和

1. 题目描述

2. 思路分析

• 经典求最大子段和，定义dp[i]为以i为结尾的子段的最大和。
• 显然，如果dp[i-1]非负，就可以累加，dp[i]=a[i]+dp[i-1]；
• 否则，放弃前边一段，重新起段，dp[i] = a[i]。
• 最后，我们发现状态转移只和上层有关，因此可以空间优化，实现O(1)的复杂度。

3. 代码实现

class Solution:


    # def maxSubArray(self, nums: List[int]) -> int:
        # n = len(nums)
        # dp = [0] * n
        # dp[0] = nums[0]
        # for i in range(1,n):
        # if dp[i-1] <= 0:
        # dp[i] = nums[i]
        # else:
        # dp[i] = nums[i] + dp[i-1]
        # return max(dp)


    def maxSubArray(self, nums: List[int]) -> int:
        n  = len(nums)
        dp = nums[0]
        ans = dp
        for a in nums[1:]:            
            dp = a if dp <= 0 else dp + a
            if ans < dp :
                ans = dp
        return ans