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）的情况。