CLRS（第 3 版）中的最大子数组和导致错误

Question

这是我早期 about CLRS(3rd edition) 的延续，如果您想了解算法，这是迄今为止您可以使用的最糟糕的书。到目前为止，我看到的第 4 章之前的所有伪代码示例都有错误，从一个错误到 wrong/missing 递归函数的基本情况，需要完全重新设计的糟糕设计选择，例如：在合并中使用标记值排序在我之前提到的另一个问题中得到解决。这本书被夸大了，完全是垃圾。

在下面的例子中，objective是求和最大的连续子数组

ex: [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

序列：18, 20, -7, 12：43

ex: [4, 5]

序列：4, 5：9

def max_crossing_subarray(a, low, mid, high):
    left_sum = -float('inf')
    total = 0
    max_left = None
    for i in range(mid, low - 1, -1):
        total += a[i]
        if total > left_sum:
            left_sum = total
            max_left = i
    right_sum = -float('inf')
    total = 0
    max_right = None
    for i in range(mid + 1, high):
        total += a[i]
        if total > right_sum:
            right_sum = total
            max_right = i
    return max_left, max_right, left_sum + right_sum

def max_subarray(a, low, high):
    if high - low == 1:  # `high == low` is wrong and results in recursion error
        return low, high, a[low]
    else:
        mid = (low + high) // 2
        left_low, left_high, left_sum = max_subarray(a, low, mid)
        right_low, right_high, right_sum = max_subarray(a, mid, high)
        cross_low, cross_high, cross_sum = max_crossing_subarray(a, low, mid, high)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_low, left_high, left_sum
        if right_sum >= left_sum and right_sum >= cross_sum:
            return right_low, right_high, right_sum
        else:
            return cross_low, cross_high, cross_sum

它适用于某些示例：列表大小 > 2，否则失败：

s1 = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
s2 = [2]
s3 = [4, 5]
for s in s1, s2, s3:
    print(s)
    print(max_subarray(s, 0, len(s)))
    print(70 * '=')

结果：

[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
(7, 10, 43)  # correct sum, inclusive indices are correct
======================================================================
[2]
(0, 1, 2)  # correct sum, exclusive indices are correct
======================================================================
[4, 5]
(1, 2, 5)  # all wrong
======================================================================

问题：代码生成 wrong/inconsistent 结果，有什么问题吗？为什么？如何修复？

Answer 1

书中给出的代码将low和high视为包含索引。所以首先你对该方法的调用应该是

print(max_subarray(s, 0, len(s)-1))

max_subarray() 没有递归问题，if 条件应保留为 if low == high:。

子数组右半部分的调用应该有mid + 1

right_low, right_high, right_sum = max_subarray(a, mid+1, high)

而在max_crossing_subarray()中，循环条件应该是for i in range(mid + 1, high + 1):.

进行所有这些更改后，输出变为：

[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
(7, 10, 43)
======================================================================
[2]
(0, 0, 2)
======================================================================
[4, 5]
(0, 1, 9)
======================================================================

CLRS（第 3 版）中的最大子数组和导致错误

Max subarray sum in CLRS (3rd edition) resulting in error

python

clrs