毎日1つのアルゴリズム問題--leetcode 53--最大サブシーケンスと(動的計画)--python

【タイトル説明】
【コード構想】
1 Dダイナミックプランニングの問題です.ステータス移行方程式は次のとおりです.
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)

効果を見ると、時間の複雑さは線形です.