毎日1つのアルゴリズム問題--leetcode 53--最大サブシーケンスと(動的計画)--python
629 ワード
【タイトル説明】
【コード構想】
1 Dダイナミックプランニングの問題です.ステータス移行方程式は次のとおりです.
dp[i]=max(nums[i],dp[i-1]+nums[i])【上コード】
効果を見ると、時間の複雑さは線形です.
【コード構想】
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)
効果を見ると、時間の複雑さは線形です.