Sıralı düzende bir milyon tam sayılar ve ardışık çift arasındaki fark eşit olduğu uzun subsequence bulmak istiyorum. Örneğin

1, 4, 5, 7, 8, 12

bir subsequence vardır

   4,       8, 12

Saf benim yöntem her noktadan bir subsequence genişletebilirsiniz nasıl açgözlü ve sadece denetler. Bu gibi nokta başına O(n²) zaman alır.

Hızlı bir şekilde bu sorunu çözmek için vardır?

Güncelleme.Kodu cevaplar içinde verilen en kısa sürede (teşekkürler) test edeceğim. Ancak n^2 bellek kullanarak çalışmayacak açık zaten. Şimdiye kadar [random.randint(0,100000) for r in xrange(200000)] olarak giriş ile sona erer kod yok .

Zamanlamaları.32 bit benim sistem aşağıdaki giriş verileri ile test ettim.

a= [random.randint(0,10000) for r in xrange(20000)] 
a.sort()

• ZelluX dinamik programlama yöntemi RAM 1.6 G kullanır ve 2 dakika 14 saniye sürüyor. Pypy sadece 9 saniye sürüyor! Ancak büyük girdilere bellek hatası ile çöküyor.
• Armin ve O(nd) süresi yöntemi pypy ile 9 saniye sürdü ama RAM sadece 20 MB. Tabii ki bu aralık çok daha geniş olsaydı çok daha kötü olurdu. Düşük bellek kullanımı da bir test anlamına geliyordu= [random.randint(0,100000) xrange r(200000)] ama pypy ile verdim birkaç dakika içinde bitirmek değildi.

Kluev yöntemi test edebilmek için ben ile tekrar araştırdık

a= [random.randint(0,40000) for r in xrange(28000)] 
a = list(set(a))
a.sort()

uzunluk listesi 20000 kabaca olun. Pypy ile tüm zamanlara

• , 9 saniye ZelluX
• , 20 Kluev saniye
• 52 saniye Armin

Eğer ZelluX yöntemi doğrusal uzay olmak üzere açık galibi olacak gibi görünüyor.

Çok az bellek ihtiyacı var, adapte senin tarafından ile 12* *bir çözüm olabilir. Burada n sayı verilen karakter dizisi öğe sayısını ve m Aralık, yani en yüksek sayıyı eksi bir en düşük.

Tüm giriş numaralarını dizisini Ara (ve sürekli set() cevap önceden hesaplanan bir soru kullanın "Bu Bir numara mı?"). Çağrı dadımsubsequence için (bu subsequence iki sayı arasındaki fark) arıyoruz. Her olası değeri d aşağıdakilerden doğrusal tarama Üzerinde tüm giriş numaraları: her sayı n Bir artan sipariş, numarası yoktu zaten, bak ileri Bir uzunluğu dizisi başlıyor n ile bir adım d. Sonra da zaten yine onlardan aramak zorunda kalmazsınız, böylece, aynı d görüldüğü gibi, sırayla tüm öğeleri işaretleyin. Bu nedenle, karmaşıklığı sadece O(n) d her değer için.

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'

Güncellemeler:

• Bu çözüm ise d <= 1000 en iyi sonucu almak yeterli olurdu eğer sadece nispeten küçük; örneğin d değerleri ilgileniyorsanız eğer yeterince iyi olabilir. O zaman karmaşıklığı aşağı O(n*1000) gider. Bu algoritma approximative, ama n=1000000 aslında çalıştırılabilir yapar. (Ölçülen 400-500 PyPy, 0 ve 10 sayılar arasında rastgele bir alt kümesi ile'000'000.) ile, 80-90 CPython saniye saniye

• Eğer hala istiyor aramak için bütün aralığı, ve eğer bu yaygın bir durum olduğunu uzun dizileri var, önemli bir gelişmedir durdurmak için en kısa sürede d çok büyük olduğu için bir daha da uzun süre sıra bulunmak.