1

我的程序似乎不适用于此代码。我是 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, low, mid, high) 工作正常,但在我的一生中,我似乎无法找到函数 find_maximum_subarray_recursive(A, low, high) 的错误。它导致程序溢出。我不明白逻辑或语法是否有问题。如果有人可以向我解释这一点,我将不胜感激。非常感谢!

4

1 回答 1

2
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)计算mid3 并调用find_maximum_subarray_recursive(A, 0, 3)以查找left_sum。但是那个 3 值被丢弃并替换为 6。所以下一个函数计算mid3 的 a 并调用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。最大和为 8,来自子数组 [3, 4, -5, 6]。

但至少你不再溢出了!

于 2014-09-10T18:28:29.790 回答