Kadane算法中的全局_最大值

Question

我读卡丹；{a1}中的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

问题在于，是否将空数组视为每个可能的子数组的子数组。p>

在这种情况下，对于隐式空数组，只有负值的数组的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.