可能更简单的O（n）解决方案，以找到具有最大平均值的长度为K（或更多）的子阵列

Question

我在编码竞赛网站上看到了这个问题。

假设给出一个n个整数和一个整数k（n <= 10 ^ 5,1 <= k <= n）的数组。如何找到长度大于k的最大平均值的子阵列（连续）。

研究论文（arxiv.org/abs/cs/0207026。）中提供了一个O（n）解决方案，链接在一个重复的SO question中。我发布这是一个单独的问题，因为我认为我有一个类似的方法，更简单的解释。您认为我的逻辑在下面的解决方案中有什么问题吗？

这是逻辑：

1. 从[i，j] = [0，K-1]开始窗口范围。然后迭代剩余的元素。
2. 对于每个下一个元素j，更新前缀sum **。现在我们可以选择 - 我们可以使用全范围[i，j]或丢弃范围[i：j-k]并保留[j-k + 1：j]（即保留最新的K元素）。选择具有较高平均值的范围（使用前缀和在O（1）中执行此操作）。
3. 跟踪每一步的最大平均值
4. 最后返回最大平均值

**我在迭代数组时计算前缀和。 i处的前缀和是数组中前i个元素的累积和。

码：

def findMaxAverage(nums, k):
    prefix = [0]
    for i in range(k):
        prefix.append(float(prefix[-1] + nums[i]))
    mavg = prefix[-1]/k
    lbound = -1
    for i in range(k,len(nums)):
        prefix.append(prefix[-1] + nums[i])
        cavg = (prefix[i+1] - prefix[lbound+1])/(i-lbound)
        altavg = (prefix[i+1] - prefix[i-k+1])/k
        if altavg > cavg:
            lbound = i-k
            cavg = altavg
        mavg = max(mavg, cavg)

    return mavg

Answer 1

考虑k = 3和序列

3,0,0,2,0,1,3

你的程序输出是1.3333333333333333。它已经找到了后续的0,1,3，但最好的子序列是2,0,1,3，平均1.5。