3

最長の算術累進部分列の問題は次のとおりです。整数 A の配列が与えられた場合、その中の最長の等差数列を見つけるアルゴリズムを考案します。言い換えると、A[i1]、A[i2]、…、A[ik] が等差数列を形成し、k が最大になるようなシーケンス i1 < i2 < … < ik を見つけます。次のコードは、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。

ただし、最大 1 つの値が欠落している等差数列を見つけられるようにしたいと考えています。したがって、arr = [1,4,5,8,10,13] の場合、値が 1 つ欠落している長さ 5 の進行があることを報告したいと思います。

これは効率的に行うことができますか？

4

1 に答える 1

1

Longest equal-spaced subsequenceへの私の回答から適応。 nは の長さ、Aはd範囲、つまり最大のアイテムから最小のアイテムを引いたものです。

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

for d in range(1, 13):
    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)
            # if there is a hole to jump over:
            if b + 2 * d in Aset:
                b += 2 * d
                count += 1
                while b + d in Aset:
                    b += d
                    count += 1
                    # don't record in already_seen here
            print "found %d items in %d .. %d" % (count, a, b)
            # collect here the largest 'count'

O(n*d)2 つの入れ子になった "for" ループ内に 2 つの "while" ループがあるにもかかわらず、この解決策は穴なしで見るよりも単純に定数が大きいだけであると思います。確かに、 の値を修正してdくださいn。しかし、内側の 2 つの while ループのそれぞれが、 のnすべての値に対して合計でほとんどの回数実行されるaため、再び複雑O(n+n+n) = O(n)になります。

元のように、このソリューションは、絶対的な最良の答えには関心がなく、比較的小さなステップのサブシーケンスにのみ関心がある場合に適応できますd。たとえばn、1'000'000 かもしれませんが、サブシーケンスのみに関心があります最大で 1,000 ステップ。次に、外側のループを 1'000 で停止させることができます。

于 2013-08-14T09:27:35.290 に答える