[动态规划]Leetcode53.最大子序和

如果读者对于动态规划思路解法还不是很了解，可以先点击链接查阅我之前的一篇博文《算法之【动态规划】详解》，很详细的介绍了动态规划求解思路及方法，有利于你更好的学习动态规划。

题目描述

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

示例1

输入: [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

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

DP定义及状态方程

定义dp[i]表示以i索引为结尾的最大连续子序列的和，因此递推方程为dp[i] = max(nums[i], dp[i-1] + nums[i]),因为如何nums[i]为负值时，dp[i]的最大值应该为dp[i-1]

此题目的最终答案即为dp数组中的最大值：max(dp)

初始边界条件

#初始化边界条件
dp[0] = nums[0]
• 1
• 2

最终代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        n = len(nums)
        dp = [float('-inf')] * n
        dp[0] = nums[0]
        for j in range(1, n):
            dp[j] = max(nums[j],dp[j-1] + nums[j])
        return max(dp)