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

- PenguinProgrammer

---

你的问题是学习一些关于动态规划的好理由。https://dev59.com/L3NA5IYBdhLWcg3wKam3 - Tyler

Answer 1

最大子序和问题

来自维基百科:

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

- ffledgling

---

我已经尝试了一段时间，但是如何使用它来确定子数组的起始和结束索引呢？ - PenguinProgrammer

Answer 2

这是一个美味的习语沙拉：

def bentley(a):
    return max((sum(a[x:y+1]), x, y) 
                for x, _ in enumerate(a) for y, _ in enumerate(a))[1:]

- dansalmo