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

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

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

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

考虑 k = 3 和序列

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

您的程序的输出是 1.3333333333333333。它找到了子序列 0,1,3,但最好的子序列是 2,0,1,3,平均 1.5