给定整数数组，找到具有最大和的连续子数组(至少包含一个数字)并返回其和
发布于2019-08-20 11:54 阅读(1043) 评论(0) 点赞(15) 收藏(5)
可采用动态规划算法，自底向上求解：
考虑到对于数组中每个位置，只要求得以该位置为末节点的连续子数组长度的最大和，即可得到最终结果：
f(n) = max( f(n-1) + array[n], array[n] )
def maxSubArray(self, nums: List[int]) -> int:
cur = -float('inf')
maxValue = -float('inf')
for i in range(len(nums)):
# cur描述了以当前节点为末节点的最大连续子串和
cur = max(cur + nums[i], nums[i])
maxValue = max(cur, maxValue)
return maxValue
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
所属网站分类: 技术文章 > 博客
作者：黎明要到来了
链接：https://www.pythonheidong.com/blog/article/49157/cd6d9a6ae3dd714e1e21/
来源：python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力