Алгоритмический вопрос дня — 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)

Глядя на эффект, временная сложность линейна: