53. Maximum Subarray
问题
给定一个整数数组 nums
,找到最大和的连续子数组(至少包含一个元素)并返回它的和。
例子:
下一步:
如果你已经找到了 O(n) 的解决方案,那么尝试使用分治法编写另一个解决方案,这种方法更加微妙。
思路
这个题目我们暂且用一个比较简单的动态规划来解决。核心思想就是最大子数列的头一定是个正数(因为负数的头对最大子数列和没有积极影响):如果前面的累加结果为负数,那么我们就可以不要了。值得注意的是,这是动态规划最经典的题目之一,是 Jon Bentley 在1984年 ACM 交流会提出的。
答案
最后更新于