Python|动态规划之最大子序和

题目描述给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1]的和最大，为 6。解决方案对于此题，将采用动态规划进行分析：对数组的每一个下标所能得到的最大值进行记录；通过判断上一个下标的最大值是否大于0，大于0则用当前下标所对应的值加上上一个下标。反之，小于则不取上一个下标的最大值(因为若是上一个下标所对应的数组最大值小于0，那么当前下标的数组最大和就等于它本身)。动态递推公式：dp[i] = max(dp[i-1], 0)+nums[i]代码示例：class Solution:def maxSubArray(self, nums: List[int]) -> int:dp = [0 for _ in range(len(nums))]dp[0], max_sums = nums[0], nums[0]for i in range(1, len(nums)):dp[i] = max(dp[i-1], 0)+nums[i]max_sums = max(max_sums, dp[i])return max_sums结语本题是一道简单的动态规划的题目，更多的是对动态规划的理解与记忆，希望对读者有所帮助。主  编   |   王楠岚责  编   |   WZY能力越强，责任越大。实事求是，严谨细致。——where2go 团队微信号：算法与编程之美