Kadane's Algorithm

From Algorithmist

Kadane's Algorithm is an O(n) algorithm for finding the maximum contiguous subsequence in a one-dimensional sequence.

[edit] Pseudocode

The algorithm keeps track of the tentative maximum subsequence in max. It accumulates a partial sum in curr and updates the optimal range when this partial sum becomes larger than max.

Kadane's Algorithm(arr[1..n])
begin
    (max, a, b) := (-INFINITY, 0, 0)
    curr := 0
    aa := 1
    for bb := 1 to n do
        curr := curr + arr[bb]
        if curr > max then
            (max, a, b) := (curr, aa, bb)
        endif

        if curr < 0 then
            curr := 0
            aa := bb + 1
        endif
    endfor

    return (max, a, b)
end