c++ - 给定一个 N 个数的数组，求出范围为 R 的所有长度的序列的个数？

Question

这是对 Given a sequence of N numbers ,extract number of sequences of length K having range less than R? 的后续问题

我基本上需要一个 vector v 作为大小 N 的答案，这样 V[i] 表示长度为 i 的序列数，其范围为 <=R。

Answer 1

传统上，在递归解决方案中，您会计算 K = 0、K = 1 的解决方案，然后找到后续元素之间的某种递推关系，以避免每次都从头开始重新计算解决方案。

但是在这里，我相信从另一边解决问题可能会很有趣，因为传播的特性:

Given a sequence of spread R (or less), any subsequence has a spread inferior to R as well

因此，我将首先建立一个从每个索引开始的展开 R 的最长子序列列表。让我们称这个列表为M , 并有 M[i] = j其中 j是S中较高的指数(原始序列)S[j] - S[i] <= R .这将是 O(N)。

现在，对于任何i , 长度的序列数 K从 i 开始是 0或 1 ，这取决于是否 K大于 M[i] - i或不。一个简单的线性传递 M (从 0 到 N-K )给了我们答案。这又是 O(N)。

所以，如果我们调用 V结果 vector ，带有 V[k]表示长度为 K 的子序列数在 S差价低于R ，然后我们可以在 M 上的单次迭代中完成:

for i in [0, len(M)]:
    for k in [0, M[i] - i]:
        ++V[k]

算法很简单，但是更新的次数可能会让人望而生畏。在最坏的情况下，假设比 M[i] - i等于 N - i ，它是 O(N*N) 的复杂度。您需要更好的数据结构(可能是 Fenwick 树的改编版)才能使用此算法，从而降低计算这些数字的成本。