最长算术级数子序列问题如下。给定一个整数数组A,设计一个算法来找出其中最长的算术级数。换句话说,找到序列i1<;i2<;…<;ik,这样a[i1]、[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的级数,但缺少一个值。在
这能有效地完成吗?在
改编自我对Longest equally-spaced subsequence的回答。
n
是A
的长度,d
是范围,即最大项减去最小项。在我相信这个解决方案仍然是
O(n*d)
,只是有比没有洞的查找更大的常量,尽管两个嵌套的“for”循环中有两个“while”循环。实际上,修复一个d
的值:那么我们就处于运行n
次的“a”循环中;但是内部两个while循环中的每一个循环在a
的所有值上总共最多运行n
次,这又给了一个复杂度O(n+n+n) = O(n)
。在与原始方案一样,此解决方案适用于这样的情况:您对绝对最佳答案不感兴趣,而只对步骤相对较小的子序列
d
感兴趣:例如,n
可能是1'000'000,但您只对最多1'000步的子序列感兴趣。然后你可以让外环停在1000英尺处。在相关问题 更多 >
编程相关推荐