在指定长度python3.5的O（n^2）下求正整数列表的最大和

Question

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

条件：

1<；=w<；=l<；=100000

列表中的每个元素的范围为[1100]

目前，我的解决方案是在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

您的解决方案确实是O(n^2)（或者{}，如果您想要一个更紧的边界）

您可以在O（n）中创建一个辅助数组sums，其中：

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

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

您甚至可以动态计算sums数组以减少空间复杂性，但如果我是您，我会从它开始，然后看看是否可以升级我的解决方案。在

Answer 2

1）找到第一个w元素的和current，将其分配给best。
2） 从i = w:current = current + lst[i]-lst[i-w]，best = max(best, current)。
3） 完成了。在