Я слежу за книгой «Введение в алгоритм» и использую алгоритм, заданный для создания программы, но программа работает не так, как ожидалось.
Возможно, сумма предыдущей функции складывается с новой суммой итаким образом это напечатано, я не знаю как.Когда я помещаю один список элементов, результат получается ожидаемым, но когда я ставлю 2 или более списка элементов, скажем [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] # [low, high, sum], но для [2,3] и [2,5] я получил вывод в виде [0, 0, 4] и [1, 1, 5] соответственно, что не соответствует ожиданиям.