Leetcode-53.最大サブシーケンス和

Leetcode-53.最大サブシーケンス和
整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列には少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.
例:
入力:[−2,1,−3,4,−1,2,1,−5,4],出力:6解釈:連続サブ配列[4,−1,2,1]の和が最大で6であった.ステップ:
複雑度O(n)の解法を実現した場合は,より優れた分治法を用いて解くことを試みた.
考え方:
ダイナミックプランニングの採用
dp[i]は、iで終わる連続サブシーケンスの最大値を意味する

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

実行時間:52 ms、すべてのpythonコミットで95.41%のユーザーを破った
メモリ消費量:12.9 MB、すべてのpythonコミットで5.12%のユーザーを破った