具有分而治之的连续值的最小和

Question

给出随机整数数组

N = [1,...,n]

我需要使用分治法来找到两个连续值的最小和。什么不是我的智商在这里工作？

def minSum(array):
    if len(array) < 2:
        return array[0]+array[1]

    if (len(a)%2) != 0:
        mid = int(len(array)/2)
        leftArray = array[:mid]
        rightArray = array[mid+1:]
        return min(minSum(leftArray),minSum(rightArray),crossSum(array,mid))
    else:
        mid = int(len(array)/2)
        leftArray = array[:mid]
        rightArray = array[mid:]
        return min(minSum(leftArray), minSum(rightArray), array[mid]+array[mid+1])


def crossSum(array,mid):
    return min(array[mid-1]+array[mid],array[mid]+array[mid+1])

Answer 1

主要问题似乎是第一个条件是错误的：如果len(array) < 2，则下一行必然会引发一个IndexError。另外，未定义a。我假设那是外部作用域中数组的名称，因此这不会引发异常，而只是默默地使用了错误的数组。除此之外，该功能似乎或多或少地起作用（不过，并未对其进行彻底的测试。

但是，您实际上不需要检查数组的长度是奇数还是偶数，两种情况都可以使用相同的代码，因此不需要使用crossSum函数。另外，将返回最小和的函数称为maxSum有点令人困惑。如果您真的想要分而治之的方法，请尝试以下方法：

def minSum(array):
    if len(array) < 2:
        return 10**100
    elif len(array) == 2:
        return array[0]+array[1]
    else:
        # len >= 3 -> both halves guaranteed non-empty
        mid = len(array) // 2
        leftArray = array[:mid]
        rightArray = array[mid:]
        return min(minSum(leftArray),
                   minSum(rightArray),
                   leftArray[-1] + rightArray[0])

import random
lst = [random.randint(1, 10) for _ in range(20)]
r = minSum(lst)
print(lst)
print(r)

随机示例输出：

[1, 5, 6, 4, 1, 2, 2, 10, 7, 10, 8, 4, 9, 5, 7, 6, 5, 1, 4, 9]
3

但是，简单的循环会更适合该问题：

def minSum(array):
    return min(array[i-1] + array[i] for i in range(1, len(array)))