algorithm - 整数数组中具有最大和的子序列

This question already has answers here:

Maximum sum sublist?
（13个答案）
给定整数数组，如何找到两个索引i和j，使得在索引处开始和结束的子数组中的元素的总和最大化，在线性时间内？

最佳答案

从我的programming pearls副本中：

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    /* invariant: maxendinghere and maxsofar are accurate
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)