arrays - 可能更简单的 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 .我将其作为一个单独的问题发布，因为我认为我有一个类似的方法，但解释更简单。您认为我在下面的解决方案中的逻辑有什么问题吗？

逻辑是这样的:

1. 从 [i,j] = [0,K-1] 的窗口范围开始。然后遍历剩余的元素。
2. 对于每个下一个元素 j，更新前缀和**。现在我们有一个选择 - 我们可以使用整个范围 [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 .