小开

你现在的解是 O(N^3)(你说的是 O(N^2) per index) ，这里是时间的 O(N^2)和存储器的 O(N^2)。

主意

如果我们知道子序列通过指数 i[0]，i[1]，i[2]，i[3]，我们不应该尝试以 i[1]和 i[2]或 i[2]和 i[3]开始的子序列

注意，我编辑这段代码是为了使使用 a排序更容易一些，但它不适用于相同的元素。你可以很容易地检查 O(N)中相等元素的最大数目

伪代码

我只是寻求最大长度，但这不会改变任何事情

whereInA = {}
for i in range(n):
whereInA[a[i]] = i; // It doesn't matter which of same elements it points to


boolean usedPairs[n][n];


for i in range(n):
for j in range(i + 1, n):
if usedPair[i][j]:
continue; // do not do anything. It was in one of prev sequences.


usedPair[i][j] = true;


//here quite stupid solution:
diff = a[j] - a[i];
if diff == 0:
continue; // we can't work with that
lastIndex = j
currentLen = 2
while whereInA contains index a[lastIndex] + diff :
nextIndex = whereInA[a[lastIndex] + diff]
usedPair[lastIndex][nextIndex] = true
++currentLen
lastIndex = nextIndex


// you may store all indicies here
maxLen = max(maxLen, currentLen)

关于内存使用的思考

对于1000000个元素，O(n^2)时间是非常慢。但是，如果要在这么多元素上运行此代码，最大的问题将是内存使用。
可以做些什么来减少它？

将布尔值数组更改为位字段，以便每位存储更多布尔值。
使每个下一个布尔数组更短，因为我们只使用 usedPairs[i][j]，如果 i < j

一些启发:

只存储使用过的索引对。(与第一个想法相冲突)
删除永远不会使用更多的 usedPair (对于这样的 i，在循环中已经选择的 j)

小开

算法

遍历列表的主循环
如果在预计算列表中找到数字，那么它属于该列表中的所有序列，用 count + 1重新计算所有序列
删除当前元素的所有预计算
重新计算新的序列，其中第一个元素的范围从0到当前，第二个是当前元素的遍历(实际上，不是从0到当前，我们可以使用这个事实，新元素不应该超过 max (a)和新列表应该有可能变得更长，已经找到一个)

因此，对于 list [1, 2, 4, 5, 7]输出将是(它有点混乱，自己尝试编写代码并查看)

指数 0，元素 1:
- 如果 1在前钙化? 不-什么也不做
- 什么都别做
指数 1，元素 2:
- 如果 2在前钙化? 不-什么也不做
- 检查在我们的集合中3 = 1 + (2-1) * 2? 不-什么也不做
指数 2，元素 4:
- 如果 4在前钙化? 不-什么也不做
  - 在我们的集合中检查 6 = 2 + (4-2) * 2? 不
  - 检查我们的集合中 7 = 1 + (4-1) * 2？是-添加新元素 {7: {3: {'count': 2, 'start': 1}}} 7元素的列表，3是步骤。
指数 3，元素 5:
- 如果 5在前钙化? 不-什么也不做
  - 不要检查 4，因为 6 = 4 + (5-4) * 2小于计算元素 7
  - 在我们的集合中检查 8 = 2 + (5-2) * 2? 不
  - 检查 10 = 2 + (5-1) * 2-大于 max (a) = = 7
指数 4，元素 7:
- 如果 7在前加法? 是的-把它变成结果
  - 不要检查 5，因为 9 = 5 + (7-5) * 2大于 max (a) = = 7

Result = (3，{‘ count’: 3，‘ start’: 1}) # 第3步，count 3，start 1，将其转换为序列

复杂性

它不应该大于 O (N ^ 2) ，我认为这是因为搜索新序列的结束时间提前了，我稍后将尝试提供详细的分析

密码

def add_precalc(precalc, start, step, count, res, N):
if step == 0: return True
if start + step * res[1]["count"] > N: return False


x = start + step * count
if x > N or x < 0: return False


if precalc[x] is None: return True


if step not in precalc[x]:
precalc[x][step] = {"start":start, "count":count}


return True


def work(a):
precalc = [None] * (max(a) + 1)
for x in a: precalc[x] = {}
N, m = max(a), 0
ind = {x:i for i, x in enumerate(a)}


res = (0, {"start":0, "count":0})
for i, x in enumerate(a):
for el in precalc[x].iteritems():
el[1]["count"] += 1
if el[1]["count"] > res[1]["count"]: res = el
add_precalc(precalc, el[1]["start"], el[0], el[1]["count"], res, N)
t = el[1]["start"] + el[0] * el[1]["count"]
if t in ind and ind[t] > m:
m = ind[t]
precalc[x] = None


for y in a[i - m - 1::-1]:
if not add_precalc(precalc, y, x - y, 2, res, N): break


return [x * res[0] + res[1]["start"] for x in range(res[1]["count"])]

小开

我们可以有一个解决方案 O(n*m)的时间与很少的内存需求，通过适应你的。这里的 n是给定数字输入序列中的项目数，而 m是范围，即最高的数字减去最低的数字。

调用所有输入数字的序列 A (并使用预先计算好的 set()在恒定时间内回答“这个数字在 A 中吗?”).调用我们正在寻找的子序列的台阶(这个子序列的两个数字之间的差)。对于 d 的每一个可能值，对所有的输入数字进行以下的线性扫描: 对于从 A 开始的每一个数字 n，如果这个数字还没有被看到，那么在 A 中查找从 n 开始的序列的长度，步骤 d。然后将该序列中的所有项目标记为已经看到的，这样我们就可以避免从它们中再次搜索同一个 d。因此，对于 d 的每个值，复杂度只是 O(n)。

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


for d in range(1, 12):
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)
print "found %d items in %d .. %d" % (count, a, b)
# collect here the largest 'count'

更新:

如果您只对相对较小的 d 值感兴趣，那么这个解决方案可能就足够好了; 例如，如果获得 d <= 1000的最佳结果就足够好了。然后复杂性下降到 O(n*1000)。这使得算法近似，但实际上可以在 n=1000000上运行。(使用 CPython 测量400-500秒，使用 PyPy 测量80-90秒，使用0到10’000’000之间的随机数子集。)
如果您仍然希望搜索整个范围，并且常见的情况是存在较长的序列，那么一个显著的改进是，一旦 d 太大，无法找到更长的序列时就停止搜索。

小开

遍历数组，记录最佳结果/s 和一个包含

(1)索引-元素在序列中的差异,
(2)到目前为止序列中元素的计数，以及
(3)最后记录的元素。

对于每个数组元素，查看与前一个数组元素的差异; 如果该元素是表中索引的序列中的最后一个元素，调整表中的序列，并在适用的情况下更新最佳序列，否则启动一个新序列，除非当前最大值大于可能序列的长度。

当 d 大于数组范围的中间时，或者当当前 max 大于可能序列的长度时，我们可以停止扫描，因为 d 大于最大索引差。其中 s[j]大于序列中最后一个元素的序列将被删除。

我将我的代码从 JavaScript 转换为 Python (我的第一个 Python 代码) :

import random
import timeit
import sys


#s = [1,4,5,7,8,12]
#s = [2, 6, 7, 10, 13, 14, 17, 18, 21, 22, 23, 25, 28, 32, 39, 40, 41, 44, 45, 46, 49, 50, 51, 52, 53, 63, 66, 67, 68, 69, 71, 72, 74, 75, 76, 79, 80, 82, 86, 95, 97, 101, 110, 111, 112, 114, 115, 120, 124, 125, 129, 131, 132, 136, 137, 138, 139, 140, 144, 145, 147, 151, 153, 157, 159, 161, 163, 165, 169, 172, 173, 175, 178, 179, 182, 185, 186, 188, 195]
#s = [0, 6, 7, 10, 11, 12, 16, 18, 19]


m = [random.randint(1,40000) for r in xrange(20000)]
s = list(set(m))
s.sort()


lenS = len(s)
halfRange = (s[lenS-1] - s[0]) // 2


while s[lenS-1] - s[lenS-2] > halfRange:
s.pop()
lenS -= 1
halfRange = (s[lenS-1] - s[0]) // 2


while s[1] - s[0] > halfRange:
s.pop(0)
lenS -=1
halfRange = (s[lenS-1] - s[0]) // 2


n = lenS


largest = (s[n-1] - s[0]) // 2
#largest = 1000 #set the maximum size of d searched


maxS = s[n-1]
maxD = 0
maxSeq = 0
hCount = [None]*(largest + 1)
hLast = [None]*(largest + 1)
best = {}


start = timeit.default_timer()


for i in range(1,n):


sys.stdout.write(repr(i)+"\r")


for j in range(i-1,-1,-1):
d = s[i] - s[j]
numLeft = n - i
if d != 0:
maxPossible = (maxS - s[i]) // d + 2
else:
maxPossible = numLeft + 2
ok = numLeft + 2 > maxSeq and maxPossible > maxSeq


if d > largest or (d > maxD and not ok):
break


if hLast[d] != None:
found = False
for k in range (len(hLast[d])-1,-1,-1):
tmpLast = hLast[d][k]
if tmpLast == j:
found = True
hLast[d][k] = i
hCount[d][k] += 1
tmpCount = hCount[d][k]
if tmpCount > maxSeq:
maxSeq = tmpCount
best = {'len': tmpCount, 'd': d, 'last': i}
elif s[tmpLast] < s[j]:
del hLast[d][k]
del hCount[d][k]
if not found and ok:
hLast[d].append(i)
hCount[d].append(2)
elif ok:
if d > maxD:
maxD = d
hLast[d] = [i]
hCount[d] = [2]




end = timeit.default_timer()
seconds = (end - start)


#print (hCount)
#print (hLast)
print(best)
print(seconds)

小开

这是我的两分钱。

如果您有一个名为 input 的列表:

input = [1, 4, 5, 7, 8, 12]

你可以建立一个数据结构，对于每一个点(不包括第一个点) ，它会告诉你这个点离它的前辈有多远:

[1, 4, 5, 7, 8, 12]
x  3  4  6  7  11   # distance from point i to point 0
x  x  1  3  4   8   # distance from point i to point 1
x  x  x  2  3   7   # distance from point i to point 2
x  x  x  x  1   5   # distance from point i to point 3
x  x  x  x  x   4   # distance from point i to point 4

现在已经有了列，可以考虑输入的 i-th项(即 input[i])和它的列中的每个数字 n。

属于包括 input[i]在内的一系列等距数字的数字是那些在其列的 i-th位置有 n * j的数字，其中 j是从左向右移动列时已经找到的匹配数，加上 input[i]的 k-th前身，其中 k是 input[i]列中 n的索引。

例如: 如果我们考虑 i = 1，input[i] = 4，n = 3，那么，我们可以识别一个包含 4(input[i]) ，7(因为它在其列的 1位置有一个 3)和 1的序列，因为 k是0，所以我们取 input[i] = 40的第一个前身。

可能的实现(如果代码没有使用与解释相同的表示法，那么很抱歉) :

def build_columns(l):
columns = {}
for x in l[1:]:
col = []
for y in l[:l.index(x)]:
col.append(x - y)
columns[x] = col
return columns


def algo(input, columns):
seqs = []
for index1, number in enumerate(input[1:]):
index1 += 1 #first item was sliced
for index2, distance in enumerate(columns[number]):
seq = []
seq.append(input[index2]) # k-th pred
seq.append(number)
matches = 1
for successor in input[index1 + 1 :]:
column = columns[successor]
if column[index1] == distance * matches:
matches += 1
seq.append(successor)
if (len(seq) > 2):
seqs.append(seq)
return seqs

最长的一个:

print max(sequences, key=len)

小开

最佳答案

更新: 这里描述的第一个算法被 Armin Rigo 的第二个回答所取代，它更加简单和有效。但这两种方法都有一个缺点。他们需要很多小时才能找到一百万个整数的结果。因此，我尝试了两个更多的变体(参见这个答案的后半部分) ，其中假定输入整数的范围是有限的。这种限制允许更快的算法。我还试着优化了 Armin Rigo 的代码。最后查看我的基准测试结果。

这里有一个使用 O (N)存储器的算法的想法。时间复杂度为 O (N² log N) ，但可以降低到 O (N²)。

算法使用以下数据结构:

prev: 指向前一个子序列元素(可能不完整)的索引数组。
带键的散列表 = 子序列中连续对之间的差值和另外两个散列表。对于这些其他散列映射: key = 子序列的开始/结束索引，value = 对(子序列长度，子序列的结束/开始索引)。
pq: 存储在 prev和 hash中的子序列的所有可能的“差”值的优先级队列。

算法:

使用索引 i-1初始化 prev。更新 hash和 pq以注册在此步骤中发现的所有(不完整)子序列及其“差异”。
从 pq获取(并删除)最小的“差异”。从 hash获取相应的记录，并扫描其中一个二级哈希映射。此时，所有具有给定“差”的子序列都已完成。如果第二级哈希映射包含的子序列长度比目前为止找到的更好，则更新最佳结果。
在数组 prev中: 对于在步骤 # 2中找到的任何序列的每个元素，减少索引并更新 hash，可能还包括 pq。在更新 hash时，我们可以执行以下操作之一: 添加一个长度为1的新子序列，或将一些现有子序列增长1，或合并两个现有子序列。
删除在步骤 # 2中找到的散列映射记录。
当 pq不是空的时候，从步骤 # 2继续。

该算法每次更新 prev O (N)的 O (N)元素。这些更新中的每一个都可能需要向 pq添加一个新的“差异”。如果我们对 pq使用简单的堆实现，所有这些都意味着 O (N² log N)的时间复杂性。为了将其减少到 O (N²) ，我们可以使用更高级的优先级队列实现。本页列出了一些可能性: 优先队列。

请参阅理念上相应的 Python 代码。此代码不允许列表中的重复元素。修复这个问题是可能的，但是无论如何，删除重复项是一个很好的优化(并且可以分别找到除重复项之外最长的子序列)。

这里的搜索在子序列长度乘以可能的子序列“差异”超过源列表范围时立即终止。

Armin Rigo 的代码简单高效。但在某些情况下，它会做一些可以避免的额外计算。当子序列长度乘以可能的子序列“差异”超过源列表范围时，搜索可以立即终止:

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]))

如果源数据(M)中的整数范围很小，那么使用 O (M²)时间和 O (M)空间可以得到一个简单的算法:

def findLESS(src):
r = [False for i in range(src[-1]+1)]
for x in src:
r[x] = True


d = 1
best = 1


while best * d < len(r):
for s in range(d):
l = 0


for i in range(s, len(r), d):
if r[i]:
l += 1
best = max(best, l)
else:
l = 0


d += 1


return best




print(findLESS([1, 4, 5, 7, 8, 12]))

它类似于 ArminRigo 的第一个方法，但是它不使用任何动态数据结构。我认为源数据没有副本。并且(为了保持代码简单)我还假设最小输入值是非负的并且接近于零。

如果我们使用位集数据结构和位操作来并行处理数据，而不使用布尔数组，那么以前的算法可能会得到改进。下面显示的代码将位集实现为一个内置的 Python 整数。它有相同的假设: 没有重复，最小输入值是非负和接近零。时间复杂度为 O (M² * log L) ，其中 L 是最优子序列的长度，空间复杂度为 O (M) :

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

基准:

输入数据(大约100000个整数)是这样生成的:

random.seed(42)
s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))

对于最快的算法，我还使用了以下数据(大约1000000个整数) :

s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))

所有结果以秒为单位显示时间:

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

小开

更新: 我找到了一篇关于这个问题的论文，你可以下载给你。

这是一个基于动态编程的解决方案。它需要 O (n ^ 2)时间复杂度和 O (n ^ 2)空间复杂度，并且不使用散列。

我们假设所有数字按升序保存在数组 a中，而 n保存其长度。2D 阵列 l[i][j]定义以 a[i]和 a[j]结束的最长等间隔子序列的长度，如果 a[j]-a[i] = a[k]-a[j](i < j < k) ，则 l[j][k] = l[i][j] + 1。

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

小开

这里是另一个答案，工作在时间 O(n^2)和没有任何显着的内存需求以外，把列表成为一个集合。

这个想法很天真: 就像原始海报一样，它是贪婪的，只是检查你能从每对点扩展一个子序列到什么程度——然而，首先检查我们是否在一个子序列的开始。换句话说，从点 a和 b你可以检查多远，你可以延伸到 b + (b-a)，b + 2*(b-a)，... 但只有当 a - (b-a)是不是已经在所有点的集合。如果是，那么您已经看到了相同的后续行为。

诀窍在于说服自己，这种简单的优化足以将复杂性从原来的 O(n^3)降低到 O(n^2)。这是留给读者的一个练习: ——)这里的时间与其他 O(n^2)解决方案相竞争。

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


lmax = 2
for j, b in enumerate(A):
for i in range(j):
a = A[i]
step = b - a
if b + step in Aset and a - step not in Aset:
c = b + step
count = 3
while c + step in Aset:
c += step
count += 1
#print "found %d items in %d .. %d" % (count, a, c)
if count > lmax:
lmax = count


print lmax

小开

这是这里描述的更一般的问题的特殊情况: 发现长期模式，其中 K = 1并且是固定的。证明了它可以在 O (N ^ 2)中求解。在我的32位机器上运行我提出的 C 算法的实现需要3秒钟才能找到 N = 20000和 M = 28000的解。

小开

贪婪的方法
1. 只生成一个决策序列。
2. 生成许多决策。动态编程 1. 它不能保证总是给出最优解。
2. 这绝对是一个最优的解决方案。

最长等间距子序列

主意

伪代码

关于内存使用的思考