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。

但至少你不会溢出！