编写程序,查找和最大的子序列。例如:{2,3,-6,-1,2,-1,6,4,- 8,8}
第二种方法是使用一个循环遍历数组,从左到右扫描数组并对元素求和。一旦得到负和,就可以从下一个元素重新开始求和。想想为什么这是正确的!在每一步中,我们检查当前的和是否大于当前的最大值。
我不清楚这个解决方案是如何工作的…虽然我用另一种方法解决了这个问题,但我不能就此罢休,因为我不明白这个解决方案。你能解释一下吗?提前感谢你的帮助。
编辑:我通过另一种方式解决了这个任务,而不是通过我不理解的东西:)
因此,正如您所述,您在一个循环中遍历数组并累积sum S
。在每一步你做S += a[i]
,你比较你的S
和当前的最大值,如max = Math.max(S, a[i])
。
你的问题是为什么我们要零S
当S < 0
。假设它发生在步骤i
。Then (S + a[i+1]) < a[i+1]
(因为S <0).由于我们正在寻找最大的后续和,因此最好从a[i+1]
开始新的子序列,即设置S = 0
。