【题目描述】
【代码思路】一维动态规划问题,状态转移方程为:
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)
复制代码
看效果,时间复杂度线性: