在CLRS（第3版）中，最大子数组和问题的算法（第4.1节）存在一个小错误。算法中有一处语句：
if left_sum + right_sum > sum:
sum = left_sum + right_sum
这里的判断条件应为 left_sum + right_sum >= sum 而非 left_sum + right_sum > sum。这是因为当 left_sum + right_sum = sum 时，更新 sum 的语句应被执行，否则会导致结果错误。
下面是一个改正后的示例代码：
def find_max_crossing_subarray(A, low, mid, high):
left_sum = float("-inf")
max_left = mid
total = 0
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")
max_right = mid + 1
total = 0
for j in range(mid+1, high+1):
total += A[j]
if total > right_sum:
right_sum = total
max_right = j
return (max_left, max_right, left_sum + right_sum)
def find_maximum_subarray(A, low, high):
if high == low:
return (low, high, A[low])
else:
mid = (low + high) // 2
(left_low, left_high, left_sum) = find_maximum_subarray(A, low, mid)
(right_low, right_high, right_sum) = find_maximum_subarray(A, mid+1, high)
(cross_low, cross_high, cross_sum) = find_max_crossing_subarray(A, low, mid, high)
if left_sum >= right_sum and left_sum >= cross_sum:
return (left_low, left_high, left_sum)
elif right_sum >= left_sum and right_sum >= cross_sum:
return (right_low, right_high, right_sum)
else:
return (cross_low, cross_high, cross_sum)
社区干货
特惠活动
CLRS（第3版）中最大子数组和情况下的错误
-优选内容
CLRS（第3版）中最大子数组和情况下的错误
-相关内容