LeetCode0053.最大子数组与【简单】【Python】【动态编程】题目LeetCode给定一个整数数组nums，找出连续的子数组（至少包含一个数）和最大的和返回其总和。示例：输入：[-2,1,-3,4,-1,2,1,-5,4]，输出：6解释：[4,-1,2,1]的总和最大=6.跟进：如果您已经找出O(n)解决方案，请尝试使用分而治之的方法编写另一个解决方案，这种方法更微妙。问题是给定一个整数数组nums，找到一个具有最大总和的连续子数组（该子数组至少包含一个元素），并返回它的最大总和。示例：输入：[-2,1,-3,4,-1,2,1,-5,4]，输出：6解释：连续子数组[4,-1,2,1]的和是最大，为6。高级：如果你实现了一个复杂度为O(n)的解决方案，请尝试使用更复杂的分治法来解决它。动态规划的思想就是求dp递归公式。dp等于每个位置的个数加上前一个dp，当前一个dp为负数时，不加。时间复杂度：O(len(nums))空间复杂度：O(1)PythoncodeclassSolution(object):defmaxSubArray(self,nums):""":typenums:List[int]:rtype:int"""ifnotnums:return0dp=0sum=-0xFFFFFFFFforiinrange(len(nums)):dp=nums[i]+(dpifdp>0else0)#ifdp>0:dp=nums[i]+dp,else:dp=nums[i]sum=max(sum,dp)返回sum代码地址github链接
