シーケンス内で最長の算術進行を見つける

Question

数が増えていると仮定し、シーケンス内で最長の算術進行の長さを求めたいとします。最長の算術進行とは、[2,4,6,8]または[3,6,9,12]のような共通の差異を持つ増加するシーケンスを意味します。

たとえば、の場合は[5, 10, 14, 15, 17]、[5, 10, 15]の場合は長さ3です。

[10, 12, 13, 20, 22, 23, 30]の場合、[10, 20, 30]は長さ3の最長算術進行です。 [7, 10, 12, 13, 15, 20, 21]、[10, 15, 20]または[7, 10, 13]ため

は長さ3

このサイト https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_Longest_arithmetic_progression.jsp で最も長い等差数列あるJの周りにループすることによって、すなわち、問題にいくつかの洞察力を提供していますし、 すべての3つの要素を考慮してください。私はPythonで、このアルゴリズムを使用すると、以下のように私のコードは次のとおりです。

def length_of_AP(L): 
n = len(L) 
Table = [[0 for _ in range(n)] for _ in range(n)] 
length_of_AP = 2 

# initialise the last column of the table as all i and (n-1) pairs have lenth 2 
for i in range(n): 
     Table[i][n-1] =2 

# loop around the list and i, k such that L[i] + L[k] = 2 * L[j] 
for j in range(n - 2, 0, -1): 
     i = j - 1 
     k = j + 1 
     while i >= 0 and k < n: 
       difference = (L[i] + L[k]) - 2 * L[j] 
       if difference < 0: 
         k = k + 1 
       else: 
         if difference > 0: 
           i = i - 1 
         else: 
           Table[i][j] = Table[j][k] + 1 
           length_of_AP = max(length_of_AP, Table[i][j]) 
           k = k + 1 
           i = i - 1 
return length_of_AP 

この機能は、[1、3、4、5、7、8、9]で正常に動作しますが、それは動作しません。 [5,10,14,15,20,25,26,27,28,30,31]の場合、6を得るはずですが、4が得られます。その理由は、25,26,27、リストの中の28は、私の機能のための気をそらす要因かもしれません。どのようにして私の機能を変更して、私に望みの結果を与えるのか。

ご協力いただけると助かります。

Answer 1

はあなたのリンクに続いて第二のサンプルを実行している、それは、実際には適切なLAPに

5を見つけるのコードのようになります。 10,15,20,25,30,

しかし、適切な長さを見つけることができない。私はコードを分析するのにあまり時間をかけなかったが、

// Any 2-letter series is an AP 
    // Here we initialize only for the last column of lookup because 
    // all i and (n-1) pairs form an AP of size 2 
    for (int i=0; i<n; i++) 
     lookup[i][n-1] = 2; 

私には疑わしいと思われる。 lookupテーブルを最後の列の代わりに2で初期化する必要があると思われます。そうした場合、サンプルの正しい長さが取得され始めます。

だから、ループを "初期化" し、次のコードにあなたの3行目を変更取り除く：

# initialise whole table with 2 as all (i, j) pairs have length 2  
Table = [[2 for _ in range(n)] for _ in range(n)] 

またその

サンプルの実行：
最大AP長= 6
3 、5,7,9,11,13,15,17,

このバグが含まれていますまさに幸運のために正しい順序を実際に印刷します。私は

int sortedArr[] = new int[] {3, 4, 5, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 112, 113, 114, 115, 116, 117, 118}; 

にsortedArrを変更した場合、私は出力

最大AP長= 7
112、113、114、115、116、117、118、

を以下取得します明らかに元の8項目の長いシーケンス3, 5, 7, 9, 11, 13, 15, 17,がまだそこにあるように間違っています。

Answer 2

試しましたか？ここで
は、小さなデータセットのために、それは十分に速く実行する必要があり、迅速な力ずくの実装です：

def gen(seq): 
    diff = ((b-a, a) for a, b in it.combinations(sorted(seq), 2)) 
    for d, n in diff: 
     k = [] 
     while n in seq: 
      k.append(n) 
      n += d 
     yield (d, k) 

def arith(seq): 
    return max(gen(seq), key=lambda x: len(x[1])) 

In [1]: arith([7, 10, 12, 13, 15, 20, 21]) 
Out[1]: (3, [7, 10, 13]) 
In [2]: %timeit arith([7, 10, 12, 13, 15, 20, 21]) 
10000 loops, best of 3: 23.6 µs per loop 
In [3]: seq = {random.randrange(1000) for _ in range(100)} 
In [4]: arith(seq) 
Out[4]: (171, [229, 400, 571, 742, 913]) 
In [5]: %timeit arith(seq) 
100 loops, best of 3: 3.79 ms per loop 
In [6]: seq = {random.randrange(1000000) for _ in range(1000)} 
In [7]: arith(seq) 
Out[7]: (81261, [821349, 902610, 983871]) 
In [8]: %timeit arith(seq) 
1 loop, best of 3: 434 ms per loop