赞
踩
刚开始拿到题目,没有什么想法。但是开始分析起来的时候,就立马有思路了。
令dp[i]
表示以nums[i]
结尾时可以得到的最大子数组和。有了这个假设之后,题目就豁然开朗了。那么dp[i]只有两种情况可以分析:dp[i-1]>0
和 dp[i-1] <0
。这两种情况下,分别对应不同的操作:
if dp[i-1] > 0 : # 之前的子数组和大于0,那么可以利用这段和
dp[i] = dp[i-1] + nums[i]
else :# 之前的子数组和小于等于0,不可以累加(因为累加会变得更小)。
dp[i] = nums[i]
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
res = nums[0]
for i in range(len(nums)):
if i == 0:
dp[i] = nums[i]
else:
if dp[i-1] > 0:
dp[i] = dp[i-1] + nums[i]
else:
dp[i] = nums[i]
res = max(res, dp[i])
return res
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。