每日一道算法题--leetcode 53--最大子序和（动态规划）--python

【题目描述】

一维动态规划问题，状态转移方程为：

dp[i]=max(nums[i],dp[i-1]+nums[i]) 【上代码】

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==1:return nums[0]
        dp=[]
        dp.append(nums[0])
        for i in range(1,len(nums)):
            dp.append(max(nums[i],nums[i]+dp[i-1]))
        return max(dp)

看效果，时间复杂度线性：