Algorithmus, um minimale Teilmenge zu entfernen, um Reihenfolgenreihenfolge zu bilden

Question

Ich habe eine Situation, in der ich "Ausreißer" in einer angeblich sortierten Reihenfolge ermitteln möchte. Elemente, die die Reihenfolge unterbrechen, werden als verdächtig angesehen.

Zum Beispiel 1, 2, 3, 4, 7, 5, 6, 8, 9 die Reihenfolge ist nicht sortiert, aber wenn Sie die 7 Sie eine sortierte Folge 1, 2, 3, 4, 5, 6, 8, 9 erhalten entfernen, dies gilt auch, wenn Sie 5 und 6 entfernen, aber das ist mehr als nur die 7 entfernen (auch wenn mit eine sortierte Sequenz können Sie beliebige Elemente entfernen und haben immer noch eine sortierte Reihenfolge).

Gibt es dafür einen effizienten Algorithmus? Gibt es einen Algorithmus, der alle gleich guten Lösungen findet?

Das letztere ist zum Beispiel, wenn Sie die Sequenz 1, 3, 2, 4 haben. Sie könnten 3 entfernen, um eine sortierte Sequenz zu erhalten, aber Sie könnten auch nur 2 entfernen, um eine sortierte Sequenz zu erhalten (beide Lösungen sind gleich gut, da sie nur ein Element entfernen).

Answer 1

Dies kann in O(N²) durch dynamisches Programm oder memoisierte Rekursion erfolgen. Wenn foo(n,m) maximale Länge sortiert Teilmenge darstellt (ich glaube, Untersequenz das richtige Wort ist) aus dem Index n wenn der Index des letzten Elements wurde hinzugefügt m dann rekursive Funktion ist:

int foo(int n,int m) { 
    int res = 0; 
    // you can add this number in the current sequence 
    //if its greater than the previous element in the sequence 
    // seq is array containing the numbers 
    if (seq[n] >= seq[m]) { 
     //1 because we added this element 
     // second argument is n because n is now the last element added 
     res = 1 + foo (n+1, n); 
    } 
    // you can always skip the current element 
    // in that case m remains same 
    res = max (res, foo(n+1, m)) 

} 

Sie müssen Eckfällen Griff (Index gleich Array-Länge) und Memoization hinzufügen, damit es funktioniert, aber ich überlasse das Ihnen. Auch die wiki Seite hat eine noch schnellere Implementierung.

Answer 2

Dieses Problem ist vergleichbar mit dem Auffinden der am längsten wachsenden Subsequenz.

Ref für O (n^2) Umsetzung: http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/

und http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ für nlog (n) Umsetzung.