Всем снова здравствуйте, вынужден вернуться к этой теме, т.к изменения предложенные SkinnyJack не помогли программе запуститься. Я пробовал ее изменять, но не получается.
Вот код целиком:
__author__ = 'Denis'
def crossing_sub_arr(arr, low, mid, high):
left_sum = -1e308
buf = 0
max_left = 0
for i in range(mid, low, -1):
buf += arr[i]
if buf > left_sum:
left_sum = buf
max_left = i
right_sum = -1e308
buf = 0
max_right = 0
for j in range(mid + 1, high, 1):
buf += arr[i]
if buf > right_sum:
right_sum = buf
max_right = j
return max_left, max_right, left_sum + right_sum
def find_max_sub_arr(arr, low, high):
if high == low + 1:
return low, high, arr[low]
else:
mid = int((low + high) / 2)
left_l, left_h, left_s = find_max_sub_arr(arr, low, mid)
right_l, right_h, right_s = find_max_sub_arr(arr, mid + 1, high)
cross_l, cross_h, cross_s = crossing_sub_arr(arr, low, mid, high)
if left_s >= right_s and left_s >= cross_s:
return left_l, left_h, left_s
elif right_s >= left_s and right_s >= cross_s:
return right_l, right_h, right_s
else:
return cross_l, cross_h, cross_s
arr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
low, r, s = find_max_sub_arr(arr, 0, len(arr))
print(low, r, s)
Если использовать его то на 6 итерации когда и low, и high будут равны 2 if сравнит 2 с 3 и рекурсия зациклится.
Если убрать +1 к low во время сравнения то будет выход за пределы массива в отрезке кода:
return low, high, arr[low]
и что делать дальше я не понимаю, всем заранее спасибо.
Пользователь решил продолжить мысль 04 Августа 2015, 22:07:29:
если что, у меня python 3.4.3
Тема: поиск максимального подмассива (Прочитано 3774 раз)
