最长的带洞等差数列

Question

最长等差数列子序列问题如下。给定一个整数数组A，设计一种算法来找到其中最长的等差数列。换句话说，找到一个序列i1 < i2 < ... < ik，使得A [i1]，A [i2]，...，A [ik]形成一个等差数列，并且k是最大的。以下代码在O（n ^ 2）时间和空间中解决了该问题。（修改自http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/。）

#!/usr/bin/env python
import sys

def arithmetic(arr):
    n = len(arr)
    if (n<=2):
        return n

    llap = 2


    L = [[0]*n for i in xrange(n)]
    for i in xrange(n):
        L[i][n-1] = 2

    for j in xrange(n-2,0,-1):
        i = j-1
        k = j+1
        while (i >=0 and k <= n-1):
            if (arr[i] + arr[k] < 2*arr[j]):
                k = k + 1
            elif (arr[i] + arr[k] > 2*arr[j]):
                L[i][j] = 2
                i -= 1
            else:

                L[i][j] = L[j][k] + 1                   
                llap = max(llap, L[i][j]) 
                i = i - 1
                k = j + 1

        while (i >=0):
            L[i][j] = 2
            i -= 1
    return llap

arr = [1,4,5,7,8,10]  
print arithmetic(arr)

这将输出4。

然而，我希望能够找到算术级数，其中最多缺少一个值。因此，如果arr = [1,4,5,8,10,13]，我希望它报告长度为5的进程缺少一个值。

这可以高效地完成吗？

- Simd

---

@Keyser 这里有一个序列：1，4，7，10，13 但是缺少了7。 - Simd

哦，我没意识到你允许数字之间有空格 :) - keyser

如果您设置表格时不仅按“最后索引”和“最后元素”进行索引，而且还要考虑序列是否已经存在间隙，会怎样呢？ - Dennis Meng

不得不去维基百科查阅“等差数列”（http://en.wikipedia.org/wiki/Arithmetic_progression）... - 2rs2ts

@DennisMeng 那也是我的第一反应，但当间隙在前两个元素之间时会有些棘手。[1,5] 可能是一个 4-列表的前两个元素，或者是一个已经缺少一个元素的 2-列表的第一个和第三个元素，而你只有一个二维数组中的一个位置来存储这两个信息。 - dfan

Answer 1

本文改编自最长等差子序列问题的答案。其中n表示A序列的长度，d表示序列的范围，即最大值减去最小值。

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

for d in range(1, 13):
    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)
            # if there is a hole to jump over:
            if b + 2 * d in Aset:
                b += 2 * d
                count += 1
                while b + d in Aset:
                    b += d
                    count += 1
                    # don't record in already_seen here
            print "found %d items in %d .. %d" % (count, a, b)
            # collect here the largest 'count'

我认为这个解决方案仍然是O(n*d)，只是比没有空洞的情况下有更大的常数，尽管在两个嵌套的“for”循环中有两个“while”循环。事实上，固定一个值d：那么我们就在运行n次的“a”循环中；但每个内部的两个while循环在所有a值上总共最多运行n次，给出复杂度O(n+n+n) = O(n)。

与原始方法一样，这种解决方案适用于您不关心绝对最佳答案而只关心相对较小步长d的情况：例如，n可能是1'000'000，但您只对步长最多为1'000的子序列感兴趣。然后，您可以使外部循环停止在1'000。

- Armin Rigo