【原】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 团队

---

微信号：算法与编程之美