Kadane 算法中的 global_max 值

Question

我在最大子阵列问题中阅读了 Kadane;s 算法- 维基百科

我可以理解基本的实现

def max_subarray2(A):

    max_current = max_global = A[0]

    for x in A[1:]:

        max_current = max(x, max_current + x)

    if max_current> max_global:

        max_global = max_current 

    return max_global

声明的数据max_current = max_global = A[0]

至于检索开始和结束索引的版本

def max_subarray3(A):

    max_current = A[0]

    startOld = start = end = max_global = 0

    for i, x in enumerate(A[1:], 1):

        max_current = max(x, max_current + x)

        max_global = max(max_global, max_current)

        if max_current < 0:

            start = i + 1

        elif max_current == max_global: #when max_global not change

            startOld = start

            end = i

    return (max_global , startOld, end)

现在max_global = 0而不是max_global = A[0]，我不知道为什么。如果所有数字都是负数，则返回 (0, 0, 1)

Answer 1

问题在于您是否将空数组视为每个可能的 A 的子数组。在这种情况下，对于隐式空数组，可以将只有负值的数组的 sum 最大值视为 0。如果您希望排除这种可能性，则需要进行相应的更改max_global = 0。这就是 0 存在的原因。您链接的文章在这里说明了很多：该算法也可以很容易地修改以跟踪最大子数组的开始和结束索引，以及如果所有元素都是负数，我们希望允许零长度子数组（隐式和为 0）的情况。