在指定长度 Python 3.5 的 O(n^2) 下的正整数列表中查找子列表的最大总和

Question

对于我的一个编程问题，我需要定义一个接受两个变量的函数，一个长度为l的列表和一个整数w。然后，我必须找到列表中长度为 w 的子列表的最大总和。

条件：

1<=w<=l<=100000

列表中的每个元素的范围从 [1， 100]

目前，我的解决方案在 O(n^2( 中工作(如果我错了，请纠正我，代码附在下面(，自动评分器不接受，因为我们需要找到一个更简单的解决方案。

我的代码：

def find_best_location(w, lst):
    best = 0
    n = 0
    while n <= len(lst) - w:
        lists = lst[n: n + w]
        cur = sum(lists)
        best = cur if cur>best else best
        n+=1
    return best

如果有人能够找到更有效的解决方案，请告诉我！另外，如果我错误地计算了我的大O符号，也请告诉我！

提前感谢！

Answer 1

1(找到前w元素的总和current，将其分配给best。
2(从i = w开始：current = current + lst[i]-lst[i-w]，best = max(best, current)。
3(完成。

Answer 2

你的解决方案确实是O(n^2)的(如果你想要更严格的界限，O(n*W)(

你可以在 O(n( 中通过创建一个 aux 数组sums来做到这一点，其中：

sums[0] = l[0]
sums[i] = sums[i-1] + l[i]

然后，通过迭代它并检查sums[i] - sums[i-W]您可以在线性时间内找到您的解决方案

您甚至可以即时计算sums数组以降低空间复杂性，但如果我是你，我会从它开始，看看接下来是否可以升级我的解决方案。