在指定长度的 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) 完成。

Answer 2

你的解决方案确实是O(n^2)（或者O(n*W)，如果你想要更严格的约束）

您可以通过创建辅助数组 sums 在 O(n) 中完成此操作，其中：

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

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

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

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

Find maximum sum of sublist in list of positive integers under O(n^2) of specified length Python 3.5

python

algorithm

sublist

maximize