1, 4, 5, 7, 8, 12

   4,       8, 12

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

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

更新： ArminRigo的第二个答案已废除了这里描述的第一个算法，该算法更简单，更有效。但是这两种方法都有一个缺点。他们需要许多小时才能找到一百万个整数的结果。因此，我尝试了另外两个变体（请参阅此答案的后半部分），其中假定输入整数的范围是有限的。这种限制允许更快的算法。我也尝试优化Armin
Rigo的代码。最后查看我的基准测试结果。

---

这是使用O（N）内存的算法思想。时间复杂度为O（N 2 log N），但可以降低为O（N 2）。

算法使用以下数据结构：

1. prev：索引数组，指向（可能不完整）子序列的前一个元素。
2. hash：具有key的hashmap =子序列中的连续对之间的差，value =另外两个hashmap。对于这些其他哈希图：键=子序列的开始/结束索引，值=对（子序列长度，子序列的结束/开始索引）。
3. pq：优先级队列，用于存储在prev和中的子序列的所有可能的“差异”值hash。

算法：

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

该算法prev每次更新O（N）次的O（N）个元素。并且这些更新中的每一个都可能需要向添加新的“差异”
pq。如果我们使用的简单堆实现，所有这些都意味着O（N 2 log N）的时间复杂度pq。为了将其减少到O（N
2），我们可以使用更高级的优先级队列实现。此页面上列出了一些可能性：优先队列。

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

和相同的代码经过一点优化。只要子序列长度乘以可能的子序列“差异”超过源列表范围，搜索就会终止。

---

Armin
Rigo的代码简单而高效。但是在某些情况下，它会执行一些额外的计算，这些计算可以避免。只要子序列长度乘以可能的子序列“差异”超过源列表范围，搜索就会终止：

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 2）时间和O（M）空间的简单算法：

def findLESS(src):
  r = [False for i in range(src[-1]+1)]
  for x in src:
    r[x] = True

  d = 1
  best = 1

  while best * d < len(r):
    for s in range(d):
      l = 0

      for i in range(s, len(r), d):
        if r[i]:
          l += 1
          best = max(best, l)
        else:
          l = 0

    d += 1

  return best


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

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

---

如果我们使用位集数据结构和按位运算来并行处理数据，而不是布尔数组，则可以改进以前的算法。下面显示的代码将位集实现为内置的Python整数。它具有相同的假设：没有重复项，最小输入值是非负值并且接近零。时间复杂度为O（M
2 * log L），其中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