对于我的一个编程问题,我需要定义一个接受两个变量的函数,一个长度为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符号,也要让我知道!在
提前谢谢!在
您的解决方案确实是},如果您想要一个更紧的边界)
O(n^2)
(或者{您可以在O(n)中创建一个辅助数组
sums
,其中:然后,通过迭代并检查
sums[i] - sums[i-W]
,你可以在线性时间内找到你的解您甚至可以动态计算
sums
数组以减少空间复杂性,但如果我是您,我会从它开始,然后看看是否可以升级我的解决方案。在1)找到第一个
w
元素的和current
,将其分配给best
。2) 从
i = w
:current = current + lst[i]-lst[i-w]
,best = max(best, current)
。3) 完成了。在
相关问题 更多 >
编程相关推荐