【题目描述】

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

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)复制代码

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