[算法]寻找最长等差数列

[Joe-C-Ding]

描述

• 输入：一个升序数组
• 输出：该数组中包含的最长等差子列

例

• 输入：3 5 6 7 10
• 输出：3 5 7 (5 6 7 也行，等长输出一个即可)

背景

主要以 cc-数学兴趣班-幼儿园-安道尔 在群里提的 寻找素数等差数列 问题为背景。假设已经用筛法生成了一个需要的素数数组，发现在里面寻找等差数列并不容易，所以抽象出该问题。

抛砖引玉

目前我能想到的方法：等差数列就是要找 a + k d，现在我的想法就是暴力枚举 a 和 d 这两个参数。
比如对于前例（记为 {n}）

3 5 6 7 10

我想找以 3 为首的数列，即 a = 3，考虑数组 {n-a}

0 2 3 4 7

让 d 枚举这其中的数字，比如 d = 2 时，计算 { (n-a)/d }

0 1 1.5 2 3.5

然后再在里面找是否存在 0 ... k 这样的连续整数能构成一个等差数列。发现间断就可以存下最大 k ，如果大于之前找到的最大 k，更新 a, d, k 这三个参数。最后可以根据这三个参数输出结果。时间复杂度大约是 O(n^3)，空间复杂度O(1)。

大家如果有其它算法可以交流下 :)

[Joe-C-Ding]

对于原始问题如果有好想法也可以说。
比如我发现要找长度大于 k 的子列， a 必须大于 k，否则 a + ad 必有因子 a。但除此之外，没发现其它什么能加速找子列的条件，所以这个抽象里也没加相应的限制。

[guofei9987]

投降了。。。

target=[3,5,6,7,9,10]
n=len(target)
target_dict={}
for i,a in enumerate(target[:-2]):
    for j,b in enumerate(target[i+1:-1]):
        target_dict[(a,b)]=0
        for i in range(2,n):
            if a+(b-a)*i in target:
                target_dict[(a,b)]+=1
            else:break
               
sorted(target_dict.items(), key=lambda d:d[1], reverse = True)[0]

[Joe-C-Ding]

像是个好主意：能稍微解释一下第 3 点么？ @guofei9987

乍一想，n^2 个数统计众数的复杂度是 O(n^2 log n)？再加上笛卡尔积是 O(n^2)，应该能快一些。空间复杂度是O(n^2)。