分而治之的连续值的最小总和

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)))

分而治之的连续值的最小总和

min sum of consecutive values with Divide and Conquer

python

arrays

algorithm

recursion

divide-and-conquer