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

Question

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

条件:

1<=w<=l<=100000

列表中每个元素的取值范围是[1, 100]

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

我的代码:

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) 完成。