最长等距后继

Question

我有一百万个按排序顺序排列的整数，我想找出最长的子序列，其中连续对之间的差相等。例如

1, 4, 5, 7, 8, 12

有一个子序列

^{pr2}$

我天真的方法是贪婪的，只是检查从每个点可以扩展子序列的距离。这似乎每点花费O(n²)时间。在

有没有更快的方法来解决这个问题？在

更新。我会尽快测试答案中给出的代码（谢谢）。但是很明显，使用n^2内存是行不通的。到目前为止，还没有以[random.randint(0,100000) for r in xrange(200000)]作为输入终止的代码。在

计时。我在32位系统上用以下输入数据进行了测试。在

a= [random.randint(0,10000) for r in xrange(20000)] 
a.sort()

• ZelluX的动态规划方法使用1.6G内存，耗时2分14秒。用pypy只需要9秒！但是，在大的输入上，它会崩溃并出现内存错误。在
• Armin的O（nd）time方法使用pypy耗时9秒，但RAM只有20MB。当然，如果射程大得多，情况会更糟。低内存使用率意味着我也可以用a=[随机.randint（0100000）在xrange（200000）中的r，但是它没有在几分钟内完成，我用pypy给出了它。在

为了能够测试Kluev的方法，我用

a= [random.randint(0,40000) for r in xrange(28000)] 
a = list(set(a))
a.sort()

列一个大致长度的列表20000。所有的时间都和pypy在一起

• 泽勒克斯，9秒
• 克鲁夫，20秒
• 阿明，52秒

看来，如果ZelluX方法可以成为线性空间，它将是明显的赢家。在

Answer 1

更新：这里描述的第一个算法被Armin Rigo's second answer淘汰，它更加简单和高效。但这两种方法都有一个缺点。他们需要很多小时才能找到一百万个整数的结果。因此，我又尝试了两个变量（见本答案的后半部分），其中假设输入整数的范围是有限的。这样的限制允许更快的算法。我还试着优化阿明·里戈的代码。最后看我的基准测试结果。在

---

这是一个使用O（N）内存的算法的思想。时间复杂度为O（N²logn），但可以降低到O（N²）。在

算法使用以下数据结构：

1. prev：指向子序列的前一个元素（可能不完整）的索引数组。在
2. hash:hashmap，key=difference between continued pairs in subsequence，value=2个其他hashmap。对于这些其他哈希映射：key=子序列的起始/结束索引，value=pair of（子序列长度，子序列的结束/开始索引）。在
3. pq：存储在prev和hash中的子序列的所有可能的“差异”值的优先级队列。在

算法：

1. 使用索引i-1初始化{}。更新hash和{}，以注册在此步骤中找到的所有（不完整）子序列及其“差异”。在
2. 从pq获取（并删除）最小的“差异”。从hash获取相应的记录并扫描其中一个二级哈希映射。此时具有给定“差”的所有子序列都是完整的。如果二级哈希映射包含的子序列长度比目前发现的要好，则更新最佳结果。在
3. 在数组prev：对于在步骤2中找到的任何序列的每个元素，递减索引并更新hash，可能还有{}。在更新hash时，我们可以执行以下操作之一：添加长度为1的新子序列，或将某些现有子序列增长1，或合并两个现有子序列。在
4. 删除步骤2中找到的哈希映射记录。在
5. 当pq不为空时，从步骤2继续。在

此算法每次更新prevO（N）个元素次。这些更新中的每一个都可能需要为pq添加一个新的“差异”。如果我们对pq使用简单的堆实现，这意味着O（N²logn）的时间复杂性。为了将其减少到O（N²），我们可以使用更高级的优先级队列实现。本页列出了一些可能性：Priority Queues。在

请参见Ideone上相应的Python代码。此代码不允许列表中有重复的元素。解决这个问题是可能的，但无论如何，删除重复项（并分别找到重复项之外最长的子序列）将是一个很好的优化。在

和the same code after a little optimization。在这里，只要子序列长度乘以可能的子序列“差异”超过源列表范围，搜索就终止。在

---

阿明·里戈的代码很简单，效率很高。但在某些情况下，它会进行一些可以避免的额外计算。只要子序列长度乘以可能的子序列“差异”超过源列表范围，搜索就可能终止：

def findLESS(A):
  Aset = set(A)
  lmax = 2
  d = 1
  minStep = 0

  while (lmax - 1) * minStep <= A[-1] - A[0]:
    minStep = A[-1] - A[0] + 1
    for j, b in enumerate(A):
      if j+d < len(A):
        a = A[j+d]
        step = a - b
        minStep = min(minStep, step)
        if a + step in Aset and b - step not in Aset:
          c = a + step
          count = 3
          while c + step in Aset:
            c += step
            count += 1
          if count > lmax:
            lmax = count
    d += 1

  return lmax

print(findLESS([1, 4, 5, 7, 8, 12]))

---

如果源数据（M）中的整数范围很小，则可以使用O（M²）时间和O（M）空间的简单算法：

^{pr2}$

它类似于arminrigo的第一种方法，但是它没有使用任何动态数据结构。我想源数据没有重复项。并且（为了保持代码的简单性），我还假设最小输入值是非负的并且接近于零。在

---

如果我们使用位集数据结构和位操作来并行处理数据，那么前面的算法可能会得到改进。下面显示的代码将位集实现为内置的Python整数。它有相同的假设：无重复，最小输入值为非负接近于零。时间复杂度为O（M²*logl），其中L为最优子序列的长度，空间复杂度为O（M）：

def findLESS(src):
  r = 0
  for x in src:
    r |= 1 << x

  d = 1
  best = 1

  while best * d < src[-1] + 1:
    c = best
    rr = r

    while c & (c-1):
      cc = c & -c
      rr &= rr >> (cc * d)
      c &= c-1

    while c != 1:
      c = c >> 1
      rr &= rr >> (c * d)

    rr &= rr >> d

    while rr:
      rr &= rr >> d
      best += 1

    d += 1

  return best

---

基准：

输入数据（大约100000个整数）是这样生成的：

random.seed(42)
s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))

对于最快的算法，我还使用了以下数据（大约1000000个整数）：

s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))

所有结果均以秒为单位显示时间：

Size:                         100000   1000000
Second answer by Armin Rigo:     634         ?
By Armin Rigo, optimized:         64     >5000
O(M^2) algorithm:                 53      2940
O(M^2*L) algorithm:                7       711

Answer 2

更新：我发现了一篇关于这个问题的论文，你可以下载它here。在

这是一个基于动态规划的解决方案。它需要O（n^2）时间复杂度和O（n^2）空间复杂度，并且不使用哈希。在

我们假设所有数字都按升序保存在数组a中，n保存其长度。2D数组l[i][j]定义以a[i]和a[j]结尾的最长等距子序列的长度，以及l[j][k]=l[i][j]+1 ifa[j]-a[i]=a[k]-a[j]（i<；j<；k）。在

lmax = 2
l = [[2 for i in xrange(n)] for j in xrange(n)]
for mid in xrange(n - 1):
    prev = mid - 1
    succ = mid + 1
    while (prev >= 0 and succ < n):
        if a[prev] + a[succ] < a[mid] * 2:
            succ += 1
        elif a[prev] + a[succ] > a[mid] * 2:
            prev -= 1
        else:
            l[mid][succ] = l[prev][mid] + 1
            lmax = max(lmax, l[mid][succ])
            prev -= 1
            succ += 1

print lmax

Answer 3

通过调整你的方法，我们可以在几乎不需要内存的情况下及时得到一个解决方案{}。这里n是给定输入序列中的项数，m是范围，即最高的数字减去最低的数字。在

调用A所有输入数字的序列（并使用预计算的set()在恒定时间内回答问题“这个数字在A中吗？”）。称d为我们要寻找的子序列的步骤（该子序列的两个数字之间的差）。对于每个可能的d值，对所有输入的数字进行以下线性扫描：对于从A开始的每个数字n，如果还没有看到该数字，则在A中从n开始，用步骤d向前看序列的长度。然后将该序列中的所有项目标记为已经看到的，这样我们就避免再次从它们中搜索，因此，对于同一个d，复杂度仅为O(n)

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

for d in range(1, 12):
    already_seen = set()
    for a in A:
        if a not in already_seen:
            b = a
            count = 1
            while b + d in Aset:
                b += d
                count += 1
                already_seen.add(b)
            print "found %d items in %d .. %d" % (count, a, b)
            # collect here the largest 'count'

更新：

• 如果您只对相对较小的d值感兴趣，那么这个解决方案就足够了；例如，如果为d <= 1000获得最佳结果就足够了。然后复杂度下降到O(n*1000)。这使算法近似，但实际上可用于n=1000000。（用CPython测量400-500秒，用PyPy测量80-90秒，随机数子集在0到10000'000之间。）

• 如果您仍然想搜索整个范围，并且常见的情况是存在长序列，那么一个显著的改进是一旦d太大而无法找到更长的序列，就停止搜索。