python - 遍历列表以获取 python 中给定范围的最大总和

Question

我是python新手。我有一个代码，我在其中循环遍历列表以捕获给定范围 k 的最大数字总和。它工作正常，但我希望它能缩短/优化。 “k”可能会有所不同

numb = [100,33,22,200,333,1000,22]
m=0
k=2
sum1=0
temp=[]
for j in range(len(numb)-(k-1)):
   for i in range(m,k):
     temp.append(numb[i])
   if sum1 < sum(temp):
     sum1 = sum(temp)
   temp=[]
   m+=1
   k+=1
print(sum1)

答案:当 k = 3 时为 1533Ans: 1333 当 k = 2

Answer 1

您可以先将前 k 个数相加。那是您的起始总和和当前的最大值。然后沿着列表运行一个滑动窗口，添加下一个数字并删除超出窗口的那个。

def sum_k(x, k):
    m = s = sum(x[:k])
    for i, a in enumerate(x[k:]):
        b = x[i]  # number to remove
        s += a - b
        m = max(m, s)
    return m


numb = [100, 33, 22, 200, 333, 1000, 22]
print(sum_k(numb, 2), sum_k(numb, 3))

这在线性时间内运行，这是最佳的，因为您至少需要查看输入中的每个元素。

循环中的索引 i 从零到 n-k-1，因此尽管我们枚举了 x[k:]我们选择的索引来自 x[0:]，因此当我们选择 b 时，我们选择的是窗口外的数字。同时，a 是进来的新数字。