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 团队微信号:算法与编程之美
赞 (0)