<p><strong>更新:</strong>这里描述的第一个算法被<a href="https://stackoverflow.com/a/18247391/1009831">Armin Rigo's second answer</a>淘汰,它更加简单和高效。但这两种方法都有一个缺点。他们需要很多小时才能找到一百万个整数的结果。因此,我又尝试了两个变量(见本答案的后半部分),其中假设输入整数的范围是有限的。这样的限制允许更快的算法。我还试着优化阿明·里戈的代码。最后看我的基准测试结果。在</p>
<hr/>
<p>这是一个使用O(N)内存的算法的思想。时间复杂度为O(N<sup>2</sup>logn),但可以降低到O(N<sup>2</sup>)。在</p>
<p>算法使用以下数据结构:</p>
<ol>
<li><code>prev</code>:指向子序列的前一个元素(可能不完整)的索引数组。在</li>
<li><code>hash</code>:hashmap,key=difference between continued pairs in subsequence,value=2个其他hashmap。对于这些其他哈希映射:key=子序列的起始/结束索引,value=pair of(子序列长度,子序列的结束/开始索引)。在</li>
<li><code>pq</code>:存储在<code>prev</code>和<code>hash</code>中的子序列的所有可能的“差异”值的优先级队列。在</li>
</ol>
<p>算法:</p>
<ol>
<li>使用索引<code>i-1</code>初始化{<cd1>}。更新<code>hash</code>和{<cd3>},以注册在此步骤中找到的所有(不完整)子序列及其“差异”。在</li>
<li>从<code>pq</code>获取(并删除)最小的“差异”。从<code>hash</code>获取相应的记录并扫描其中一个二级哈希映射。此时具有给定“差”的所有子序列都是完整的。如果二级哈希映射包含的子序列长度比目前发现的要好,则更新最佳结果。在</li>
<li>在数组<code>prev</code>:对于在步骤2中找到的任何序列的每个元素,递减索引并更新<code>hash</code>,可能还有{<cd3>}。在更新<code>hash</code>时,我们可以执行以下操作之一:添加长度为1的新子序列,或将某些现有子序列增长1,或合并两个现有子序列。在</li>
<li>删除步骤2中找到的哈希映射记录。在</li>
<li>当<code>pq</code>不为空时,从步骤2继续。在</li>
</ol>
<p>此算法每次更新<code>prev</code>O(N)个元素次。这些更新中的每一个都可能需要为<code>pq</code>添加一个新的“差异”。如果我们对<code>pq</code>使用简单的堆实现,这意味着O(N<sup>2</sup>logn)的时间复杂性。为了将其减少到O(N<sup>2</sup>),我们可以使用更高级的优先级队列实现。本页列出了一些可能性:<a href="http://www.theturingmachine.com/algorithms/heaps.html" rel="nofollow noreferrer">Priority Queues</a>。在</p>
<p>请参见<a href="http://ideone.com/h8oTYv" rel="nofollow noreferrer">Ideone</a>上相应的Python代码。此代码不允许列表中有重复的元素。解决这个问题是可能的,但无论如何,删除重复项(并分别找到重复项之外最长的子序列)将是一个很好的优化。在</p>
<p>和<a href="http://ideone.com/bW8meY" rel="nofollow noreferrer">the same code after a little optimization</a>。在这里,只要子序列长度乘以可能的子序列“差异”超过源列表范围,搜索就终止。在</p>
<hr/>
<p>阿明·里戈的代码很简单,效率很高。但在某些情况下,它会进行一些可以避免的额外计算。只要子序列长度乘以可能的子序列“差异”超过源列表范围,搜索就可能终止:</p>
<pre><code>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]))
</code></pre>
<hr/>
<p>如果源数据(M)中的整数范围很小,则可以使用O(M<sup>2</sup>)时间和O(M)空间的简单算法:</p>
^{pr2}$
<p>它类似于arminrigo的第一种方法,但是它没有使用任何动态数据结构。我想源数据没有重复项。并且(为了保持代码的简单性),我还假设最小输入值是非负的并且接近于零。在</p>
<hr/>
<p>如果我们使用位集数据结构和位操作来并行处理数据,那么前面的算法可能会得到改进。下面显示的代码将位集实现为内置的Python整数。它有相同的假设:无重复,最小输入值为非负接近于零。时间复杂度为O(M<sup>2</sup>*logl),其中L为最优子序列的长度,空间复杂度为O(M):</p>
<pre><code>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
</code></pre>
<hr/>
<p><strong>基准:</strong></p>
<p>输入数据(大约100000个整数)是这样生成的:</p>
<pre><code>random.seed(42)
s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))
</code></pre>
<p>对于最快的算法,我还使用了以下数据(大约1000000个整数):</p>
<pre><code>s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))
</code></pre>
<p>所有结果均以秒为单位显示时间:</p>
<pre><code>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
</code></pre>