kadane algorithm - any order constraints on input?

Question

I apologize if I have missed some assumption about the input but doesn't this algorithm fail for input like {2, -3, 1} ?

When processing -3, the currentSum gets 2+ (-3) = -1 and currentStartIndex starts anew! Am I overlooking something obvious?

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

Answer 1

No it doesn't - in this case, since the sum is now -1, it gets reset - which you realized.

But, prior to the reset, in the previous index, the max is saved as the value - 2 - at that time, since it is larger than 0, the previous max.

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

So in the end the algorithm will give you 2, which is the max.

This algorithm only has one issue, which is that in the case that all elements are negative it will give you 0 which means the best is an empty array. The correctness of this answer depends on if you allow empty arrays.