3

最长的算术级数子序列问题如下。给定一个整数数组 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 的级数缺少一个值。

这可以有效地完成吗？

4

1 回答 1

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 循环中的每一个在 的n所有值上最多运行一次a，再次给出了复杂性O(n+n+n) = O(n)。

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

于 2013-08-14T09:27:35.290 回答