algorithm - 找到具有足够平均分数的最长序列

Question

我有一个分数介于 0 和 1 之间的长列表。我如何有效地找到所有比 x 元素长的连续子列表，使得每个子列表中的平均分数不小于 y？

例如，如何找到所有长度超过 300 个元素的连续子列表，使得这些子列表的平均分数不低于 0.8？

我主要对满足这些条件的最长子列表感兴趣，实际上并不是所有子列表。所以我正在寻找所有最长的子列表。

Answer 1

如果您只想要最长 这样的子串，这可以在O(n log n) 时间内解决，方法是稍微转换一下问题，然后对最大值进行二分搜索解长度。

让输入的分数列表为 x[1], ..., x[n]。让我们通过从每个元素中减去 y 来转换此列表，以形成列表 z[1], ..., z[n]，其元素可以是正数或负数。请注意，任何子列表 x[i .. j] 的平均得分至少为 y 当且仅当 z 中相应子列表中元素的总和(即 z[i] + z[i+ 1] + ... + z[j]) 至少为 0。因此，如果我们有办法有效地计算 z[] 中任何子列表的最大值 总和 T(剧透:我们这样做), 作为副作用，这会告诉我们在 x[] 中是否有 any 子列表平均得分至少为 y:如果 T >= 0 则至少有 1 个这样的子列表，而如果 T < 0 则 x[] 中没有子列表(甚至不是单元素子列表)平均得分至少为 y。但这还没有为我们提供回答您最初问题所需的所有信息，因为没有任何东西强制 z 中的最大和子列表具有最大长度:很可能存在更长的子列表具有较低的总体平均值，但仍具有至少 y 的平均值。

这可以通过概括寻找具有最大总和的子列表的问题来解决:我们现在不是要求总和最大的子列表，而是要求在所有长度至少为 有些给了k。我现在将描述一个算法，给定一个数字列表 z[1], ..., z[n]，每个数字都可以是正数或负数，以及任何正整数 k，将计算任何的最大总和z[] 的子列表具有至少 k 的长度，以及达到此和的特定子列表的位置，并且在具有此和的所有子列表中具有最长的可能长度。这是 Kadane's algorithm 的略微概括。 .

FindMaxSumLongerThan(z[], k):
    v = 0                 # Sum of the rightmost k numbers in the current sublist
    For i from 1 to k:
        v = v + z[i]

    best = v
    bestStart = 1
    bestEnd = k

    # Now for each i, with k+1 <= i <= n, find the biggest sum ending at position i.
    tail = -1          # Will contain the maximum sum among all lists ending at i-k
    tailLen = 0        # The length of the longest list having the above sum
    For i from k+1 to n:
        If tail >= 0:
            tail = tail + z[i-k]
            tailLen = tailLen + 1
        Else:
            tail = z[i-k]
            tailLen = 1

        If tail >= 0:
            nonnegTail = tail
            nonnegTailLen = tailLen
        Else:
            nonnegTail = 0
            nonnegTailLen = 0

        v = v + z[i] - z[i-k]    # Slide the window right 1 position
        If v + nonnegTail > best:
            best = v + nonnegTail
            bestStart = i - k - nonnegTailLen + 1
            bestEnd = i

上述算法需要 O(n) 时间和 O(1) 空间，返回 best 中的最大总和以及在 bestStart 中实现该总和的某个子列表的开始和结束位置 和 bestEnd。

以上内容有什么用？对于给定的输入列表 x[]，假设我们首先通过从每个元素中减去 y 将 x[] 转换为 z[]，如上所述；这将是传递给每次调用 FindMaxSumLongerThan() 的 z[]。我们可以将使用 z[] 和给定的最小子列表长度 k 调用函数得到的 best 的值视为 k 的数学函数:best(k)。由于 FindMaxSumLongerThan() 找到长度至少 k 的 z[] 的任何子列表的最大和，best(k) 是 k 的非递增函数。 (假设我们设置 k=5 并发现任何子列表的最大总和为 42；那么如果我们再次尝试使用 k=4 或 k=3，我们保证找到总和至少为 42。)这意味着 我们可以对 k 进行二进制搜索以找到最大的 k 使得 best(k) >= 0:然后 k 将是 x[] 的最长子列表，其平均值至少y。生成的 bestStart 和 bestEnd 将标识具有此属性的特定子列表；在不增加时间复杂度的情况下，很容易修改算法以找到所有这些子列表(最多 n 个，每个最右边的位置一个)。