我正在学习《算法入门》一书,并使用给出的算法制作程序,但程序并没有按预期工作。
可能上一个函数的和加在了新的和上,所以我不知道怎么打印出来。
当我放置一个元素列表时,输出和预期的一样,但是当我放置两个或更多元素列表时,比如说[2,3]时,我得到了不期望的输出4
def max_crossing_subarray(array,low,mid,high):
left_sum = -1000
sum_ar = 0
for i in range(mid, low-1, -1):
sum_ar = sum_ar + array[i]
if sum_ar>left_sum:
left_sum = sum_ar
max_left = i
right_sum = -1000
sum_ar = 0
for i in range(mid,high):
sum_ar = sum_ar + array[i]
if sum_ar>right_sum:
right_sum = sum_ar
max_right = i
return [max_left, max_right, left_sum + right_sum]
def max_subarray(array, low, high):
if low==high:
return [low, high, array[low]]
else:
mid = int((low + high)/2)
left_low, left_high, left_sum = max_subarray(array, low, mid)
right_low, right_high, right_sum = max_subarray(array,mid+1,high)
cross_low, cross_high, cross_sum = max_crossing_subarray(array,
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]
arr = [2,3]
ar= max_subarray(arr, 0, len(arr)-1)
print(ar)
当我输入列表[2]时,我得到了输出[0,0,2][低,高,和]
但对于[2,3]和[2,5],我得到的输出分别为[0,0,4]和[1,1,5],这不是预期的。
最佳答案
在计算最大交叉子数组时,for语句范围的秒数应该从mid+1开始,到high+1结束。首先将中间元素right now添加到左和右和,然后在最后一个元素之前完成元素的求和。