Python数组中范围的最大总和

Question

尝试创建一个函数，其中将数组 a 作为参数传递，返回的是一对索引 x,y，使得最大和为 sum(a[x:y])。

例如，假设我有数组 [4, -2, -3, 7, 3, -1]。该函数将接收此数组并吐出 (3, 4)，因为从索引 3 到索引 4 的数字序列是您可以在此数组中创建的最大数字序列。 10 是您通过将任何序列加在一起而在此数组中找到的最大数字。

这是我到目前为止的代码，或多或少有效，但对于长度 > 10000 的数组，它需要永远。有什么建议吗？

def bentley(a):
    max = 0
    indices = 0,0
    for x in range(len(a)):
        for y in range(len(a)):
            if sum(a[x:y]) > max:
                max = sum(a[x:y])
                indices = x,y
    return indices

Answer 1

http://en.wikipedia.org/wiki/Maximum_subarray_problem

来自维基百科:

Kadane 算法，O(n)

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)

    if max_so_far > 0:
        return max_so_far
    else:
        return max(A)

---

交替分而治之 O(nlogn):

http://penguin.ewu.edu/~bojianxu/courses/cscd320/slides_dc_2.pdf