Maximum Subarray

文章目录

找出给定数组中连续子数组的最大和。比如给定数组[−2,1,−3,4,−1,2,1,−5,4]，那么将返回[4,-1,2,1]，最大和为6。

这道题目可以这样做，从头扫一遍数组，如果前两项的和为负数，说明该数在当前情况下不会做出贡献，所以我们将可能的最大值设为当前元素；如果前两项的和不为负数，那么可能的最大值为前两项的和加上当前元素。

最后将可能的最大值与之前元素的最大值，进行比较并更新。