Python代碼中的溢出錯誤使用遞歸的最大子數組

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可以接受的是len(A)-1，而不是len(A)。

忽略用戶提供的值high是造成無限循環的原因。例如，find_maximum_subarray_recursive(A, 0, 6)計算3的mid，並調用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應該是一個整數（因爲您將來使用它來索引列表，將來只列出接受整數）。你根本不需要撥打math.floor。 //運算符已經返回一個整數。我想，這行應該看起來更像：

mid = (low + high) // 2 

---

這些變化並不完全修復程序。您將得到2 3 7的結果，但7不是A的最大子數組總和。從子陣列[3，4，-5，6]中，最大的總和是8。

但至少你不會溢出！