Здравствуйте, продолжаю изучать алгоритмы, написал программу для поиска макс.подмассива, но она не работает, подскажите почему.
__author__ = 'denis'
m = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
def find_max_crossing_subarray(a, low, mid, high):
left_sum = -1e308
s = 0
for i in range(mid, low, -1):
s += a[i]
if s > left_sum:
left_sum = s
max_left = i
right_sum = -1e308
s = 0
for j in range(mid, high, 1):
s += a[j]
if s > right_sum:
right_sum = s
max_right = j
return max_left, max_right, left_sum + right_sum
def find_max_subarray(a, low, high):
if high == low:
return low, high, a[low]
else:
mid = (low + high) / 2
left_low, left_high, left_sum = find_max_subarray(a, low, mid)
right_low, right_high, right_sum = find_max_subarray(a, mid, high)
cross_low, cross_high, cross_sum = find_max_crossing_subarray(a, low, mid+1, high)
if left_sum >= right_sum and left_sum >= cross_sum:
return left_low, left_high, left_sum
if right_sum >= left_sum and right_sum >= cross_sum:
return right_low, right_high, right_sum
else:
return cross_low, cross_high, cross_sum
min, max, sum = find_max_subarray(m, 0, 15)
print(min, max, sum)
по ошибке я понял, что достигается предел глубины рекурсии, но сомневаюсь что нужно 1000 итераций для массива на 16 элементов
Пользователь решил продолжить мысль 30 Июля 2015, 16:26:00:
добавление этого кода не помогло :
import sys
sys.setrecursionlimit(100000)