在指定长度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

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