python - 最长算术级数

Question

给定一个数字列表arr(未排序)，找到其中最长的算术级数。

数组:整数a

1 ≤ arr.size() ≤ 10^3。 和-10^9 ≤ arr[i] ≤ 10^9。

示例:

arr = [7,6,1,9,7,9,5,6,1,1,4,0​​] ------------- - 输出 = [7,6,5,4]

arr = [4,4,6,7,8,13,45,67] -------------- 输出 = [4,6,8]

from itertools import combinations
def arithmeticProgression2(a):
    n=len(a)
    diff = ((y-x, x) for x, y in combinations(a, 2))
    dic=[]
    for d, n in diff:
        k = []
        seq=a
        while n in seq:
           k.append(n)
           i=seq.index(n)
           seq=seq[i+1:]
           n += d
       dic.append(k)      
   maxx=max([len(k) for k in dic])
   for x in dic:
       if len(x)==maxx:
           return x

如果arr.size()足够大。我的代码将运行超过 4000 毫秒。

示例:

arr = [randint(-10**9,10**9) for i in range(10**3)]

运行时间> 4000ms

如何降低上述解决方案的空间复杂度？

Answer 1

导致代码变慢的原因之一是您从头开始为每一对构建系列，这是没有必要的:

• 实际上您并不需要每次都构建k。如果您只保留进展的步长、长度和开始(或结束)值，您就知道了。只为最终结果显式构建进程
• 通过对每一对执行此操作，您还创建了系列，其中起点实际上位于较长系列的中间(具有相同的步骤)，因此您部分地做了双重工作，并且工作没有用处，在这种情况下，较早开始的进程显然会比当前分析的进程长。
• 它使您的代码在 O(n3) 时间内运行，而不是可能的 O(n2)。

使用动态编程，以下代码似乎可以在 O(n²) 时间内更快地返回结果:

def longestprogression(data):
    if len(data) < 3:
        return data
    maxlen = 0 # length of longest progression so far
    endvalue = None # last value of longest progression
    beststep = None # step of longest progression

    # progressions ending in index i, keyed by their step size, 
    # with the progression length as value
    dp = [{} for _ in range(len(data))]

    # iterate all possible ending pairs of progressions
    for j in range(1, len(arr)):
        for i in range(j):
            step = arr[j] - arr[i]
            if step in dp[i]:
                curlen = dp[i][step] + 1
            else:
                curlen = 2
            dp[j][step] = curlen
            if curlen > maxlen:
                maxlen = curlen
                endvalue = arr[j]
                beststep = step

    # rebuild the longest progression from the values we maintained
    return list(reversed(range(endvalue, endvalue - maxlen * beststep, -beststep)))