Ошибка переполнения кода Python для максимального Subarray с использованием рекурсии

Question

Моя программа, похоже, не работает для этого кода. Я новичок в 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, низкий, средний, высокий) работает нормально, но для жизни меня я не могу найти ошибку с помощью функции find_maximum_subarray_recursive (A, низкий, высокий). Это приводит к переполнению программы. Я не понимаю, есть ли проблема с логикой или синтаксисом. Я был бы очень признателен, если бы кто-нибудь мог объяснить это мне. Большое спасибо!

Answer 1

def find_maximum_subarray_recursive(A, low = 0, high = -1): 
    high = len(A) 

Эта строка high = len(A) выглядит как логическая ошибка для меня. Я предполагаю, что ваши оригинальные аргументы были: «Если пользователь не задает значение для параметра high, то мы предоставим его для него как самый высокий индекс, который может принять A». Если это ваше намерение, есть две проблемы: вы устанавливаете значение независимо от того, предоставил ли он сам значение.

1. .
2. наибольший индекс A может принимать is len(A)-1, а не len(A).

Игнорирование введенного пользователем значения high является причиной вашего бесконечного цикла. Например, find_maximum_subarray_recursive(A, 0, 6) вычисляет mid из 3 и звонит find_maximum_subarray_recursive(A, 0, 3), чтобы найти left_sum. Но это значение 3 выбрано и заменено на 6. Таким образом, следующая функция вычисляет mid из 3 и звонит find_maximum_subarray_recursive(A, 0, 3) ... И так далее, навсегда и всегда.

Так что я думаю, что начало функции должно выглядеть примерно так:

def find_maximum_subarray_recursive(A, low = 0, high = -1): 
    if high == -1: high = len(A)-1 

---

И еще одно:

else: 
     mid = math.floor((low + high) // 2) 

Это выглядит как ошибка типа для меня. math.floor возвращает значение с плавающей запятой, но mid должно быть целым числом (поскольку вы собираетесь использовать его для индексации списка в будущем и перечисляете только целые числа accept). Вам вообще не нужен звонок math.floor. Оператор // уже возвращает целое число. Я думаю, что эта линия должна выглядеть как:

mid = (low + high) // 2 

---

Эти изменения не полностью исправить программу. Вы получите результат 2 3 7, но 7 не является максимальной суммой субарейма для A. Самая большая сумма - 8, из подмассива [3, 4, -5, 6].

Но, по крайней мере, вы больше не переполнены!