我的程序似乎不适用于此代码。我是 Python 新手,所以我不确定这是否是与语言相关的错误。我目前正在使用 Python 2.7.8。
A = [-1, -2, 3, 4, -5, 6]
def main():
a,b,c = find_maximum_subarray_recursive(A)
print a,b,c
def find_maximum_crossing_subarray(A, low, mid, high):
#mid = math.floor((low + high)//2)
left_sum = float("-inf")
sum = 0
i = mid
max_left = 0
for i in range (mid, low, -1):
sum = sum + A[i]
if sum > left_sum:
left_sum = sum
max_left = i
right_sum = float("-inf")
sum = 0
j = mid + 1
max_right = 0
for j in range (mid + 1, high):
sum = sum + A[j]
if sum > right_sum:
right_sum = sum
max_right = j
return (max_left, max_right, left_sum + right_sum)
def find_maximum_subarray_recursive(A, low = 0, high = -1):
high = len(A)
if high == low:
return (low, high, A[low])
else:
mid = math.floor((low + high) // 2)
left_low, left_high, left_sum = find_maximum_subarray_recursive(A, low, mid)
right_low, right_high, right_sum = find_maximum_subarray_recursive(A, mid + 1, high)
cross_low, cross_high, cross_sum = find_maximum_crossing_subarray(A, low, mid, high)
if left_sum >= right_sum & left_sum >= cross_sum:
return (left_low, left_high, left_sum)
elif right_sum >= left_sum & right_sum >= cross_sum:
return (right_low, right_high, right_sum)
else:
return (cross_low, cross_high, cross_sum)
if __name__ == '__main__':main()
函数 find_maximum_crossing_subarray(A, low, mid, high) 工作正常,但在我的一生中,我似乎无法找到函数 find_maximum_subarray_recursive(A, low, high) 的错误。它导致程序溢出。我不明白逻辑或语法是否有问题。如果有人可以向我解释这一点,我将不胜感激。非常感谢!