Ich habe eine Million Ganzzahlen in sortierter Reihenfolge und möchte die längste Teilsequenz finden, bei der die Differenz zwischen aufeinanderfolgenden Paaren gleich ist. Zum Beispiel

1, 4, 5, 7, 8, 12

hat eine Folge

   4,       8, 12

Meine naive Methode ist gierig und prüft nur, wie weit Sie eine Teilsequenz von jedem Punkt aus erweitern können. Dies braucht O(n²)anscheinend Zeit pro Punkt.

Gibt es einen schnelleren Weg, um dieses Problem zu lösen?

Aktualisieren. Ich werde den in den Antworten angegebenen Code so schnell wie möglich testen (danke). Es ist jedoch bereits klar, dass die Verwendung von n ^ 2-Speicher nicht funktioniert. Bisher gibt es keinen Code, der mit der Eingabe als endet [random.randint(0,100000) for r in xrange(200000)].

Timings. Ich habe mit den folgenden Eingabedaten auf meinem 32-Bit-System getestet.

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

• Die dynamische Programmiermethode von ZelluX verwendet 1,6 GB RAM und dauert 2 Minuten und 14 Sekunden. Mit Pypy dauert es nur 9 Sekunden! Es stürzt jedoch mit einem Speicherfehler bei großen Eingaben ab.
• Die O (nd) -Zeitmethode von Armin dauerte 9 Sekunden mit Pypy, aber nur 20 MB RAM. Dies wäre natürlich viel schlimmer, wenn die Reichweite viel größer wäre. Die geringe Speichernutzung bedeutete, dass ich es auch mit a = [random.randint (0,100000) für r in xrange (200000)] testen konnte, aber es endete nicht in den wenigen Minuten, die ich es mit pypy gab.

Um die Methode von Kluevs I reran mit testen zu können

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

eine Liste der Länge grob zu machen 20000. Alle Zeiten mit Pypy

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

Es scheint, dass wenn die ZelluX-Methode linearer Raum gemacht werden könnte, es der klare Gewinner wäre.

Update: Der hier beschriebene erste Algorithmus wird durch die zweite Antwort von Armin Rigo überholt , die viel einfacher und effizienter ist. Beide Methoden haben jedoch einen Nachteil. Sie benötigen viele Stunden, um das Ergebnis für eine Million Ganzzahlen zu finden. Also habe ich zwei weitere Varianten ausprobiert (siehe zweite Hälfte dieser Antwort), bei denen angenommen wird, dass der Bereich der Eingabe-Ganzzahlen begrenzt ist. Eine solche Einschränkung ermöglicht viel schnellere Algorithmen. Außerdem habe ich versucht, den Code von Armin Rigo zu optimieren. Siehe meine Benchmarking-Ergebnisse am Ende.

Hier ist eine Idee eines Algorithmus, der einen O (N) -Speicher verwendet. Die zeitliche Komplexität beträgt O (N ² log N), kann jedoch auf O (N ² ) verringert werden .

Der Algorithmus verwendet die folgenden Datenstrukturen:

1. prev: Array von Indizes, die auf das vorherige Element der (möglicherweise unvollständigen) Teilsequenz verweisen.
2. hash: Hashmap mit Schlüssel = Differenz zwischen aufeinanderfolgenden Paaren in Teilsequenz und Wert = zwei weitere Hashmaps. Für diese anderen Hashmaps: key = Start- / Endindex der Teilsequenz, value = Paar von (Teilsequenzlänge, End- / Startindex der Teilsequenz).
3. pq: Prioritätswarteschlange für alle möglichen "Differenz" -Werte für in prevund gespeicherte Teilsequenzen hash.

Algorithmus:

1. prevMit Indizes initialisieren i-1. Aktualisieren hashund pqregistrieren Sie alle (unvollständigen) Teilsequenzen, die in diesem Schritt gefunden wurden, und ihre "Unterschiede".
2. Holen Sie sich den kleinsten "Unterschied" von (und entfernen Sie ihn) pq. Holen Sie sich den entsprechenden Datensatz hashund scannen Sie eine der Hash-Maps der zweiten Ebene. Zu diesem Zeitpunkt sind alle Teilsequenzen mit gegebener "Differenz" vollständig. Wenn die Hash-Map der zweiten Ebene eine bessere Teilsequenzlänge als bisher enthält, aktualisieren Sie das beste Ergebnis.
3. Im Array prev: Für jedes Element einer in Schritt 2 gefundenen Sequenz den Index dekrementieren und aktualisieren hashund möglicherweise pq. Während der Aktualisierung hashkönnen wir eine der folgenden Operationen ausführen: Hinzufügen einer neuen Teilsequenz der Länge 1 oder Erhöhen einer vorhandenen Teilsequenz um 1 oder Zusammenführen zweier vorhandener Teilsequenzen.
4. Entfernen Sie den in Schritt 2 gefundenen Hash-Map-Datensatz.
5. Fahren Sie mit Schritt 2 fort, solange dieser pqnicht leer ist.

Dieser Algorithmus aktualisiert jeweils O (N) Elemente von prevO (N) mal. Und für jedes dieser Updates muss möglicherweise ein neuer "Unterschied" hinzugefügt werden pq. All dies bedeutet Zeitkomplexität von O (N ² log N), wenn wir eine einfache Heap-Implementierung für verwenden pq. Um es auf O (N ² ) zu verringern, verwenden wir möglicherweise erweiterte Prioritätswarteschlangenimplementierungen. Einige der Möglichkeiten sind auf dieser Seite aufgeführt: Prioritätswarteschlangen .

Siehe entsprechenden Python-Code auf Ideone . Dieser Code erlaubt keine doppelten Elemente in der Liste. Es ist möglich, dies zu beheben, aber es wäre trotzdem eine gute Optimierung, Duplikate zu entfernen (und die längste Teilsequenz nach Duplikaten separat zu finden).

Und der gleiche Code nach ein wenig Optimierung . Hier wird die Suche beendet, sobald die Teilsequenzlänge multipliziert mit einer möglichen Teilsequenzdifferenz den Quelllistenbereich überschreitet.

Der Code von Armin Rigo ist einfach und ziemlich effizient. In einigen Fällen werden jedoch einige zusätzliche Berechnungen durchgeführt, die vermieden werden können. Die Suche kann beendet werden, sobald die Teilsequenzlänge multipliziert mit der möglichen Teilsequenzdifferenz den Quelllistenbereich überschreitet:

def findLESS(A):
  Aset = set(A)
  lmax = 2
  d = 1
  minStep = 0

  while (lmax - 1) * minStep <= A[-1] - A[0]:
    minStep = A[-1] - A[0] + 1
    for j, b in enumerate(A):
      if j+d < len(A):
        a = A[j+d]
        step = a - b
        minStep = min(minStep, step)
        if a + step in Aset and b - step not in Aset:
          c = a + step
          count = 3
          while c + step in Aset:
            c += step
            count += 1
          if count > lmax:
            lmax = count
    d += 1

  return lmax

print(findLESS([1, 4, 5, 7, 8, 12]))

Wenn der Bereich von ganzen Zahlen in den Quelldaten (M) klein ist, ist ein einfacher Algorithmus mit O (M ² ) -Zeit und O (M) -Raum möglich:

def findLESS(src):
  r = [False for i in range(src[-1]+1)]
  for x in src:
    r[x] = True

  d = 1
  best = 1

  while best * d < len(r):
    for s in range(d):
      l = 0

      for i in range(s, len(r), d):
        if r[i]:
          l += 1
          best = max(best, l)
        else:
          l = 0

    d += 1

  return best


print(findLESS([1, 4, 5, 7, 8, 12]))

Es ähnelt der ersten Methode von Armin Rigo, verwendet jedoch keine dynamischen Datenstrukturen. Ich nehme an, Quelldaten haben keine Duplikate. Und (um den Code einfach zu halten) ich nehme auch an, dass der minimale Eingabewert nicht negativ ist und nahe Null liegt.

Der vorherige Algorithmus kann verbessert werden, wenn anstelle des Arrays von Booleschen Werten eine Bitset-Datenstruktur und bitweise Operationen verwendet werden, um Daten parallel zu verarbeiten. Der unten gezeigte Code implementiert Bitset als integrierte Python-Ganzzahl. Es hat die gleichen Annahmen: keine Duplikate, minimaler Eingabewert ist nicht negativ und nahe Null. Die zeitliche Komplexität ist O (M ² * log L), wobei L die Länge der optimalen Teilsequenz ist, die räumliche Komplexität ist O (M):

def findLESS(src):
  r = 0
  for x in src:
    r |= 1 << x

  d = 1
  best = 1

  while best * d < src[-1] + 1:
    c = best
    rr = r

    while c & (c-1):
      cc = c & -c
      rr &= rr >> (cc * d)
      c &= c-1

    while c != 1:
      c = c >> 1
      rr &= rr >> (c * d)

    rr &= rr >> d

    while rr:
      rr &= rr >> d
      best += 1

    d += 1

  return best

Benchmarks:

Eingabedaten (ca. 100000 Ganzzahlen) werden folgendermaßen generiert:

random.seed(42)
s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))

Und für die schnellsten Algorithmen habe ich auch die folgenden Daten verwendet (ungefähr 1000000 Ganzzahlen):

s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))

Alle Ergebnisse zeigen die Zeit in Sekunden:

Size:                         100000   1000000
Second answer by Armin Rigo:     634         ?
By Armin Rigo, optimized:         64     >5000
O(M^2) algorithm:                 53      2940
O(M^2*L) algorithm:                7       711

Wir können O(n*m)rechtzeitig eine Lösung mit sehr geringem Speicherbedarf finden, indem wir Ihre anpassen. Hier nist die Anzahl der Elemente in der angegebenen Eingabesequenz von Zahlen und mder Bereich, dh die höchste Zahl minus die niedrigste.

Rufen Sie A die Folge aller eingegebenen Nummern auf (und verwenden Sie eine vorberechnete set()Frage, um die Frage " Ist diese Nummer in A?" In konstanter Zeit zu beantworten). Nennen Sie d den Schritt der Subsequenz, nach der wir suchen (die Differenz zwischen zwei Zahlen dieser Subsequenz). Führen Sie für jeden möglichen Wert von d den folgenden linearen Scan über alle Eingangsnummern durch: Wenn für jede Zahl n von A in aufsteigender Reihenfolge die Zahl nicht bereits gesehen wurde, suchen Sie in A nach der Länge der Sequenz, die bei n mit a beginnt Schritt d. Markieren Sie dann alle Elemente in dieser Reihenfolge als bereits gesehen, damit wir nicht erneut nach denselben Elementen suchen müssen. D. Aus diesem Grund ist die Komplexität nur O(n)für jeden Wert von d.

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'

Aktualisierung:

• Diese Lösung ist möglicherweise gut genug, wenn Sie nur an Werten von d interessiert sind, die relativ klein sind. Zum Beispiel, wenn es d <= 1000gut genug wäre, das beste Ergebnis zu erzielen. Dann geht die Komplexität auf O(n*1000). Dies macht den Algorithmus ungefähr, aber tatsächlich ausführbar für n=1000000. (Gemessen bei 400-500 Sekunden mit CPython, 80-90 Sekunden mit PyPy, mit einer zufälligen Teilmenge von Zahlen zwischen 0 und 10'000'000.)

• Wenn Sie immer noch nach dem gesamten Bereich suchen möchten und häufig lange Sequenzen vorhanden sind, besteht eine bemerkenswerte Verbesserung darin, anzuhalten, sobald d zu groß ist, um eine noch längere Sequenz zu finden.

UPDATE: Ich habe ein Papier zu diesem Problem gefunden. Sie können es hier herunterladen .

Hier ist eine Lösung, die auf dynamischer Programmierung basiert. Es erfordert O (n ^ 2) Zeitkomplexität und O (n ^ 2) Raumkomplexität und verwendet kein Hashing.

Wir gehen davon aus, dass alle Zahlen ain aufsteigender Reihenfolge im Array gespeichert sind und nihre Länge speichern. Das 2D-Array l[i][j]definiert die Länge der längsten Teilsequenz mit gleichem Abstand, die mit a[i]und endet a[j], und l[j][k]= l[i][j]+ 1, wenn a[j]- a[i]= a[k]- a[j](i <j <k).

lmax = 2
l = [[2 for i in xrange(n)] for j in xrange(n)]
for mid in xrange(n - 1):
    prev = mid - 1
    succ = mid + 1
    while (prev >= 0 and succ < n):
        if a[prev] + a[succ] < a[mid] * 2:
            succ += 1
        elif a[prev] + a[succ] > a[mid] * 2:
            prev -= 1
        else:
            l[mid][succ] = l[prev][mid] + 1
            lmax = max(lmax, l[mid][succ])
            prev -= 1
            succ += 1

print lmax

Algorithmus

• Hauptschleife durchläuft die Liste
• Wenn die Nummer in der vorberechneten Liste gefunden wurde, gehört sie zu allen Sequenzen in dieser Liste. Berechnen Sie alle Sequenzen mit count + 1 neu
• Entfernen Sie alle für das aktuelle Element vorberechneten Elemente
• Berechnen Sie neue Sequenzen neu, wobei das erste Element im Bereich von 0 bis aktuell und das zweite im aktuellen Traversalelement liegt (tatsächlich nicht von 0 bis aktuell, können wir die Tatsache verwenden, dass das neue Element nicht größer als max (a) und neu sein sollte Liste sollte die Möglichkeit haben, länger zu werden als die bereits gefundene)

Also für die Listenausgabe [1, 2, 4, 5, 7]wäre (es ist ein wenig chaotisch, versuchen Sie es selbst mit Code und sehen Sie)

• Index 0 , Element 1 :
  • wenn 1in Precalc? Nein - nichts tun
  • Nichts tun
• Index 1 , Element 2 :
  • wenn 2in Precalc? Nein - nichts tun
  • Überprüfen Sie, ob 3 = 1+ ( 2- 1) * 2 in unserem Set? Nein - nichts tun
• Index 2 , Element 4 :
  • wenn 4in Precalc? Nein - nichts tun
    • Überprüfen Sie, ob 6 = 2+ ( 4- 2) * 2 in unserem Set? Nein
    • Überprüfen Sie, ob 7 = 1+ ( 4- 1) * 2 in unserem Set? Ja - neues Element hinzufügen {7: {3: {'count': 2, 'start': 1}}} 7 - Element der Liste, 3 ist Schritt.
• Index 3 , Element 5:
  • wenn 5in Precalc? Nein - nichts tun
    • Nicht prüfen, 4da 6 = 4 + ( 5- 4) * 2 kleiner ist als das berechnete Element 7
    • Überprüfen Sie, ob 8 = 2+ ( 5- 2) * 2 in unserem Set? Nein
    • check 10 = 2+ ( 5- 1) * 2 - mehr als max (a) == 7
• Index 4 , Element 7:
  • wenn 7 in Precalc? Ja - setzen Sie es in Ergebnis
    • Nicht prüfen, 5da 9 = 5 + ( 7- 5) * 2 mehr als max (a) == 7 ist

Ergebnis = (3, {'count': 3, 'start': 1}) # Schritt 3, Count 3, Start 1, in Sequenz umwandeln

Komplexität

Es sollte nicht mehr als O (N ^ 2) sein, und ich denke, es liegt weniger an der früheren Beendigung der Suche nach neuen Sequenzen. Ich werde später versuchen, eine detaillierte Analyse bereitzustellen

Code

def add_precalc(precalc, start, step, count, res, N):
    if step == 0: return True
    if start + step * res[1]["count"] > N: return False

    x = start + step * count
    if x > N or x < 0: return False

    if precalc[x] is None: return True

    if step not in precalc[x]:
        precalc[x][step] = {"start":start, "count":count}

    return True

def work(a):
    precalc = [None] * (max(a) + 1)
    for x in a: precalc[x] = {}
    N, m = max(a), 0
    ind = {x:i for i, x in enumerate(a)}

    res = (0, {"start":0, "count":0})
    for i, x in enumerate(a):
        for el in precalc[x].iteritems():
            el[1]["count"] += 1
            if el[1]["count"] > res[1]["count"]: res = el
            add_precalc(precalc, el[1]["start"], el[0], el[1]["count"], res, N)
            t = el[1]["start"] + el[0] * el[1]["count"]
            if t in ind and ind[t] > m:
                m = ind[t]
        precalc[x] = None

        for y in a[i - m - 1::-1]:
            if not add_precalc(precalc, y, x - y, 2, res, N): break

    return [x * res[0] + res[1]["start"] for x in range(res[1]["count"])]

Hier ist eine weitere Antwort, die rechtzeitig O(n^2)und ohne nennenswerten Speicherbedarf arbeitet, der über das Verwandeln der Liste in einen Satz hinausgeht.

Die Idee ist ziemlich naiv: Wie das Originalplakat ist es gierig und prüft nur, wie weit Sie eine Teilsequenz von jedem Punktepaar aus erweitern können - prüfen Sie jedoch zuerst, ob wir am Anfang einer Teilsequenz stehen. Mit anderen Worten, von Punkten aus aund bSie überprüfen, wie weit Sie bis zu ... reichen b + (b-a)können b + 2*(b-a), aber nur, wenn dies a - (b-a)nicht bereits in der Menge aller Punkte enthalten ist. Wenn ja, haben Sie bereits dieselbe Teilsequenz gesehen.

Der Trick besteht darin, uns davon zu überzeugen, dass diese einfache Optimierung ausreicht, um die Komplexität gegenüber O(n^2)dem Original zu verringern O(n^3). Das bleibt dem Leser als Übung :-) Die Zeit ist hier konkurrenzfähig mit anderen O(n^2)Lösungen.

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

lmax = 2
for j, b in enumerate(A):
    for i in range(j):
        a = A[i]
        step = b - a
        if b + step in Aset and a - step not in Aset:
            c = b + step
            count = 3
            while c + step in Aset:
                c += step
                count += 1
            #print "found %d items in %d .. %d" % (count, a, c)
            if count > lmax:
                lmax = count

print lmax

Ihre Lösung ist O(N^3)jetzt (Sie sagten O(N^2) per index). Hier geht es um O(N^2)Zeit und O(N^2)Speicherlösung.

Idee

Wenn wir eine Subsequenz kennen, die durch Indizes i[0]geht i[1], i[2]sollten i[3]wir keine Subsequenz versuchen, die mit i[1]und i[2]oder i[2]und beginnti[3]

Hinweis: Ich habe diesen Code bearbeitet, um die Verwendung dieser aSortierung zu vereinfachen, aber er funktioniert nicht für gleiche Elemente. Sie können die maximale Anzahl gleicher Elemente O(N)einfach überprüfen

Pseudocode

Ich suche nur nach maximaler Länge, aber das ändert nichts

whereInA = {}
for i in range(n):
   whereInA[a[i]] = i; // It doesn't matter which of same elements it points to

boolean usedPairs[n][n];

for i in range(n):
    for j in range(i + 1, n):
       if usedPair[i][j]:
          continue; // do not do anything. It was in one of prev sequences.

    usedPair[i][j] = true;

    //here quite stupid solution:
    diff = a[j] - a[i];
    if diff == 0:
       continue; // we can't work with that
    lastIndex = j
    currentLen = 2
    while whereInA contains index a[lastIndex] + diff :
        nextIndex = whereInA[a[lastIndex] + diff]
        usedPair[lastIndex][nextIndex] = true
        ++currentLen
        lastIndex = nextIndex

    // you may store all indicies here
    maxLen = max(maxLen, currentLen)

Gedanken zur Speichernutzung

O(n^2)Die Zeit ist für 1000000 Elemente sehr langsam. Wenn Sie diesen Code jedoch für eine solche Anzahl von Elementen ausführen, ist das größte Problem die Speichernutzung.
Was kann getan werden, um es zu reduzieren?

• Ändern Sie boolesche Arrays in Bitfelder, um mehr Boolesche Werte pro Bit zu speichern.
• Machen Sie jedes nächste boolesche Array kürzer, da wir nur usedPairs[i][j]if verwendeni < j

Einige Heuristiken:

• Speichern Sie nur Paare gebrauchter Indikationen. (Konflikte mit der ersten Idee)
• Entfernen Sie usedPairs, die nie mehr verwendet werden (für solche i, jdie bereits in der Schleife ausgewählt wurden).

Das sind meine 2 Cent.

Wenn Sie eine Liste mit dem Namen input haben:

input = [1, 4, 5, 7, 8, 12]

Sie können eine Datenstruktur erstellen, die für jeden dieser Punkte (mit Ausnahme des ersten) angibt, wie weit dieser Punkt von einem seiner Vorgänger entfernt ist:

[1, 4, 5, 7, 8, 12]
 x  3  4  6  7  11   # distance from point i to point 0
 x  x  1  3  4   8   # distance from point i to point 1
 x  x  x  2  3   7   # distance from point i to point 2
 x  x  x  x  1   5   # distance from point i to point 3
 x  x  x  x  x   4   # distance from point i to point 4

Nachdem Sie die Spalten haben, können Sie das i-thEingabeelement (dh input[i]) und jede Zahl nin der Spalte berücksichtigen .

Die Zahlen, die zu einer Reihe von äquidistanten Zahlen gehören input[i], sind diejenigen, die n * jan der i-thPosition ihrer Spalte stehen, wobei jdie Anzahl der Übereinstimmungen, die bereits beim Verschieben von Spalten von links nach rechts gefunden wurden, plus der k-thVorgänger von input[i], wobei kder Index von ist nin der Spalte von input[i].

Beispiel: wenn man bedenkt i = 1, input[i] = 4, n = 3, dann können wir eine Sequenz identifizieren Begreifen 4( input[i]), 7(weil es eine hat 3in Position 1seiner Spalte) und 1, weil k0, so dass wir die ersten Vorgänger nehmen i.

Mögliche Implementierung (Entschuldigung, wenn der Code nicht dieselbe Notation wie die Erklärung verwendet):

def build_columns(l):
    columns = {}
    for x in l[1:]:
        col = []
        for y in l[:l.index(x)]:
            col.append(x - y)
        columns[x] = col
    return columns

def algo(input, columns):
    seqs = []
    for index1, number in enumerate(input[1:]):
        index1 += 1 #first item was sliced
        for index2, distance in enumerate(columns[number]):
            seq = []
            seq.append(input[index2]) # k-th pred
            seq.append(number)
            matches = 1
            for successor in input[index1 + 1 :]:
                column = columns[successor]
                if column[index1] == distance * matches:
                    matches += 1
                    seq.append(successor)
            if (len(seq) > 2):
                seqs.append(seq)
    return seqs

Der längste:

print max(sequences, key=len)

Durchlaufen Sie das Array und führen Sie eine Aufzeichnung der optimalen Ergebnisse und einer Tabelle mit

(1) Index - der Elementdifferenz in der Sequenz,
(2) Anzahl - Anzahl der Elemente in der Sequenz und
(3) der zuletzt aufgezeichneten Element.

Betrachten Sie für jedes Array-Element den Unterschied zu jedem vorherigen Array-Element. Wenn dieses Element das letzte in einer in der Tabelle indizierten Sequenz ist, passen Sie diese Sequenz in der Tabelle an und aktualisieren Sie gegebenenfalls die beste Sequenz. Andernfalls starten Sie eine neue Sequenz, es sei denn, das aktuelle Maximum ist größer als die Länge der möglichen Sequenz.

Wenn Sie rückwärts scannen, können Sie den Scan stoppen, wenn d größer als die Mitte des Array-Bereichs ist. oder wenn das aktuelle Maximum größer als die Länge der möglichen Sequenz ist, für d größer als die größte indizierte Differenz. Sequenzen, bei denen s[j]das letzte Element in der Sequenz größer ist, werden gelöscht.

Ich habe meinen Code von JavaScript in Python konvertiert (meinen ersten Python-Code):

import random
import timeit
import sys

#s = [1,4,5,7,8,12]
#s = [2, 6, 7, 10, 13, 14, 17, 18, 21, 22, 23, 25, 28, 32, 39, 40, 41, 44, 45, 46, 49, 50, 51, 52, 53, 63, 66, 67, 68, 69, 71, 72, 74, 75, 76, 79, 80, 82, 86, 95, 97, 101, 110, 111, 112, 114, 115, 120, 124, 125, 129, 131, 132, 136, 137, 138, 139, 140, 144, 145, 147, 151, 153, 157, 159, 161, 163, 165, 169, 172, 173, 175, 178, 179, 182, 185, 186, 188, 195]
#s = [0, 6, 7, 10, 11, 12, 16, 18, 19]

m = [random.randint(1,40000) for r in xrange(20000)]
s = list(set(m))
s.sort()

lenS = len(s)
halfRange = (s[lenS-1] - s[0]) // 2

while s[lenS-1] - s[lenS-2] > halfRange:
    s.pop()
    lenS -= 1
    halfRange = (s[lenS-1] - s[0]) // 2

while s[1] - s[0] > halfRange:
    s.pop(0)
    lenS -=1
    halfRange = (s[lenS-1] - s[0]) // 2

n = lenS

largest = (s[n-1] - s[0]) // 2
#largest = 1000 #set the maximum size of d searched

maxS = s[n-1]
maxD = 0
maxSeq = 0
hCount = [None]*(largest + 1)
hLast = [None]*(largest + 1)
best = {}

start = timeit.default_timer()

for i in range(1,n):

    sys.stdout.write(repr(i)+"\r")

    for j in range(i-1,-1,-1):
        d = s[i] - s[j]
        numLeft = n - i
        if d != 0:
            maxPossible = (maxS - s[i]) // d + 2
        else:
            maxPossible = numLeft + 2
        ok = numLeft + 2 > maxSeq and maxPossible > maxSeq

        if d > largest or (d > maxD and not ok):
            break

        if hLast[d] != None:
            found = False
            for k in range (len(hLast[d])-1,-1,-1):
                tmpLast = hLast[d][k]
                if tmpLast == j:
                    found = True
                    hLast[d][k] = i
                    hCount[d][k] += 1
                    tmpCount = hCount[d][k]
                    if tmpCount > maxSeq:
                        maxSeq = tmpCount
                        best = {'len': tmpCount, 'd': d, 'last': i}
                elif s[tmpLast] < s[j]:
                    del hLast[d][k]
                    del hCount[d][k]
            if not found and ok:
                hLast[d].append(i)
                hCount[d].append(2)
        elif ok:
            if d > maxD: 
                maxD = d
            hLast[d] = [i]
            hCount[d] = [2]


end = timeit.default_timer()
seconds = (end - start)

#print (hCount)
#print (hLast)
print(best)
print(seconds)

Dies ist ein besonderer Fall für das hier beschriebene allgemeinere Problem: Entdecken Sie lange Muster, bei denen K = 1 und fest ist. Dort wird demostriert, dass es in O (N ^ 2) gelöst werden kann. Nach der Implementierung des dort vorgeschlagenen C-Algorithmus dauert es 3 Sekunden, um die Lösung für N = 20000 und M = 28000 in meiner 32-Bit-Maschine zu finden.

Gierige Methode
1. Es wird nur eine Entscheidungssequenz generiert.
2. Es werden viele Entscheidungen getroffen. Dynamische Programmierung 1. Es ist nicht garantiert, immer eine optimale Lösung zu finden.
2. Es gibt definitiv eine optimale Lösung.