python - Kadane 算法中的 global_max 值

Question

我在 Maximum subarray problem - Wikipedia 中读到了 Kadane 的算法

我可以理解基本的实现

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 存在的原因。

您链接的文章指出了 here :

The algorithm can also be easily modified to keep track of the starting and ending indices of the maximum subarray as well as the case where we want to allow zero-length subarrays (with implicit sum 0) if all elements are negative.