algorithm - kadane 算法 - 输入的任何顺序限制？

Question

如果我错过了一些关于输入的假设，我深表歉意，但是这个算法对于像{2, -3, 1}这样的输入不会失败吗？

处理-3时， currentSum 得到2+ (-3) = -1并且 currentStartIndex 重新开始！我是否忽略了一些明显的东西？

http://www.algorithmist.com/index.php/Kadane%27s_Algorithm

Answer 1

不，它没有 - 在这种情况下，因为 sum 是 now -1，所以它会被重置 - 你意识到了。

但是，在重置之前，在之前的索引中，最大值被保存为当时的值 - 2-，因为它大于0之前的最大值。

if currentMaxSum > maxSum then
            (maxSum, maxStartIndex, maxEndIndex) := (currentMaxSum, currentStartIndex, currentEndIndex)
endif

所以最后算法会给你2，这是最大值。

这个算法只有一个问题，那就是在所有元素都是负数的情况下，它会给你0，这意味着最好的是一个空数组。这个答案的正确性取决于您是否允许空数组。