擅长:python、mysql、java
<p>更新:我发现了一篇关于这个问题的论文,你可以下载它<a href="http://www.cs.illinois.edu/~jeffe/pubs/arith.html">here</a>。在</p>
<p>这是一个基于动态规划的解决方案。它需要O(n^2)时间复杂度和O(n^2)空间复杂度,并且不使用哈希。在</p>
<p>我们假设所有数字都按升序保存在数组<code>a</code>中,<code>n</code>保存其长度。2D数组<code>l[i][j]</code>定义以<code>a[i]</code>和<code>a[j]</code>结尾的最长等距子序列的长度,以及<code>l[j][k]</code>=<code>l[i][j]</code>+1 if<code>a[j]</code>-<code>a[i]</code>=<code>a[k]</code>-<code>a[j]</code>(i<;j<;k)。在</p>
<pre><code>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
</code></pre>