maximum-contiguous-subsequence

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

Kadane算法是用于寻找一维数组最大连续子集,复杂度O(n)。

begin
    (maxSum, maxStartIndex, maxEndIndex) := (-INFINITY, 0, 0)
    currentMaxSum := 0
    currentStartIndex := 1
    for currentEndIndex := 1 to n do
        currentMaxSum := currentMaxSum + array[currentEndIndex]
        if currentMaxSum > maxSum then
            (maxSum, maxStartIndex, maxEndIndex) := (currentMaxSum, currentStartIndex, currentEndIndex)
        endif

        if currentMaxSum < 0 then
            currentMaxSum := 0
            currentStartIndex := currentEndIndex + 1
        endif
    endfor

    return (maxSum, maxStartIndex, maxEndIndex)
end
In [1]:
def max_subarray(A):
    maxSum, maxStartIndex, maxEndIndex = A[0], 0, 0
    currentMaxSum = 0
    currentStartIndex = 0
    for currentEndIndex, item in enumerate(A):
        currentMaxSum = currentMaxSum + A[currentEndIndex]
        if currentMaxSum > maxSum:
            maxSum, maxStartIndex, maxEndIndex = currentMaxSum, currentStartIndex, currentEndIndex
        if currentMaxSum < 0:
            currentMaxSum = 0
            currentStartIndex = currentEndIndex + 1
    return (maxSum, maxStartIndex, maxEndIndex, A[maxStartIndex:maxEndIndex+1])
In [2]:
x = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print u'最大连续子集:\n和为{},起止下标{}{}\n子集为{}'.format(*max_subarray(x))
最大连续子集:
和为6,起止下标3,6。
子集为[4, -1, 2, 1]
In [1]:
from IPython.display import HTML
HTML('<iframe width="800" height="500" frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=def+max_subarray(A)%3A%0D%0A++++maxSum,+maxStartIndex,+maxEndIndex+%3D+A%5B0%5D,+0,+0%0D%0A++++currentMaxSum+%3D+0%0D%0A++++currentStartIndex+%3D+0%0D%0A++++for+currentEndIndex,+item+in+enumerate(A)%3A%0D%0A++++++++currentMaxSum+%3D+currentMaxSum+%2B+A%5BcurrentEndIndex%5D%0D%0A++++++++if+currentMaxSum+%3E+maxSum%3A%0D%0A++++++++++++maxSum,+maxStartIndex,+maxEndIndex+%3D+currentMaxSum,+currentStartIndex,+currentEndIndex%0D%0A++++++++if+currentMaxSum+%3C+0%3A%0D%0A++++++++++++currentMaxSum+%3D+0%0D%0A++++++++++++currentStartIndex+%3D+currentEndIndex+%2B+1%0D%0A++++return+(maxSum,+maxStartIndex,+maxEndIndex,+A%5BmaxStartIndex%3AmaxEndIndex%2B1%5D)%0D%0A++++%0D%0Ax+%3D+%5B-2,+1,+-3,+4,+-1,+2,+1,+-5,+4%5D%0D%0A%0D%0Amax_subarray(x)&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=52&codeDivWidth=350&codeDivHeight=400"> </iframe>')
Out[1]:
In [ ]: