可能更简单的 O(n) 解决方案来找到长度为 K（或更多）的具有最大平均值的子数组

Question

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

Suppose you are given an array of n integers and an integer k (n<= 10^5, 1<=k<=n). How to find the sub-array(contiguous) with maximum average whose length is more than k.

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

逻辑如下：

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

** 我在遍历数组时计算前缀和。 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。

可能更简单的 O(n) 解决方案来找到长度为 K（或更多）的具有最大平均值的子数组

Possibly simpler O(n) solution to find the Sub-array of length K (or more) with the maximum average

arrays

algorithm

data-structures

sub-array