längste nondecreasing Teilfolge in O(nlgn)

Habe ich den folgenden Algorithmus, die gut funktioniert

Habe ich versucht zu erklären, es hier für mich http://nemo.la/?p=943 und es ist hier erklärt http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ als auch auf stackoverflow sowie

Ich möchte es ändern zu produzieren, die längste non-monoton steigende Teilfolge

für die Folge 30 20 20 10 10 10 10

die Antwort sollte 4 sein: "10 10 10 10"

Aber das mit nlgn version des Algorithmus, es funktioniert nicht. Initialisieren s enthalten das erste element "30" und ab an das zweite element = 20. Dies ist, was passiert:

  1. Den ersten Schritt: 30 nicht größer als oder gleich 20. Wir suchen das kleinste element größer als 20 sein. Der neue s wird "20"

  2. Der zweite Schritt: 20 ist größer als oder gleich 20. Wir verlängern die Sequenz und s enthält jetzt "20 20"

  3. Der Dritte Schritt: 10 ist nicht größer als oder gleich 20. Wir suchen das kleinste element größer als 10 "20". Der neue s wird "10 20"

und s wird nie wachsen nach, und der Algorithmus zurück 2 statt 4

int height[100];
int s[100];

int binary_search(int first, int last, int x) {

    int mid;

    while (first < last) {

        mid = (first + last) /2;

        if (height[s[mid]] == x)
            return mid;

        else if (height[s[mid]] >= x)
            last =  mid;

        else
            first = mid + 1;
    }
    return first; /* or last */
}

int longest_increasing_subsequence_nlgn(int n) {

    int i, k, index;

    memset(s, 0, sizeof(s));

    index = 1;
    s[1] = 0; /* s[i] = 0 is the index of the element that ends an increasing sequence of length  i = 1 */

    for (i = 1; i < n; i++) {

        if (height[i] >= height[s[index]]) { /* larger element, extend the sequence */

            index++; /* increase the length of my subsequence */
            s[index] = i; /* the current doll ends my subsequence */

        }
        /* else find the smallest element in s >= a[i], basically insert a[i] in s such that s stays sorted */
        else {
            k = binary_search(1, index, height[i]);

            if (height[s[k]] >= height[i]) { /* if truly >= greater */
                s[k] = i;
            }
        }
    }
    return index;
}
  • Durch nicht-monoton ansteigende Sequenz, meinst du nicht monoton Steigend? Das ist for every i>j: x[i]>=x[j]?
  • ja sorry, ich war verwirrend: es sollte "nondecreasing"
InformationsquelleAutor | 2014-02-12
  1. 3

    Finden die am längsten nicht-streng monoton wachsende Teilfolge, änderung dieser Bedingungen:

    1. Wenn A[i] ist das kleinste unter allen Kandidaten Ende der aktiven-Listen, beginnen wir neue aktive Liste der Länge 1.
    2. Wenn A[i] ist das größte unter allen Kandidaten Ende der aktiven Listen, wir Klonen den größten aktiven Liste, und erweitern Sie es, indem A[i].
    3. Wenn A[i] zwischen ist, finden wir eine Liste mit den größten Ende-element, das kleiner ist als A[i]. Klonen und erweitern Sie diese Liste durch A[i]. Wir verwerfen auch alle anderen Listen der gleichen Länge wie die des modifizierten Liste.

    zu:

    1. Wenn A[i] ist kleiner als die kleinste am Ende alle Kandidaten der aktiven-Listen, beginnen wir neue aktive Liste der Länge 1.
    2. Wenn A[i] ist das größte unter allen Kandidaten Ende der aktiven Listen, wir Klonen den größten aktiven Liste, und erweitern Sie es, indem A[i].
    3. Wenn A[i] zwischen ist, finden wir eine Liste mit den größten Ende-element kleiner als oder gleich A[i]. Klonen und erweitern Sie diese Liste durch A[i]. Wir verwerfen auch alle anderen Listen der gleichen Länge wie die des modifizierten Liste.

    Den vierten Schritt-für dein Beispiel-Sequenz werden sollten:

    10 ist nicht weniger als 10 (das kleinste element). Wir finden das größte element, das kleiner ist als oder gleich 10 (das wäre s[0]==10). Klonen und erweitern Sie diese Liste durch 10. Entsorgen Sie die vorhandene Liste der Länge 2. Die neue s wird {10 10}.

    • Ich werde es überprüfen und Sie wissen lassen, vielen Dank
    InformationsquelleAutor Anton
  2. 3

    Ihrem code, der fast funktioniert, bis auf ein problem in Ihrem binary_search() - Funktion, diese Funktion sollte den index des ersten Elements, das größer ist als das target-element(x), da Sie wollen, dass die längste nicht-Abnehmender Reihenfolge. Ändern Sie diese zu, es werde in Ordnung sein.

    Wenn Sie c++, std::lower_bound() und std::upper_bound() wird Ihnen helfen, loszuwerden, dieses verwirrende problem. Durch die Art und Weise, die if-Anweisung"if (height[s[k]] >= height[i])" ist überflüssig.

    int binary_search(int first, int last, int x) {

    while(last > first)
    {
        int mid = first + (last - first) /2;
        if(height[s[mid]] > x)
            last = mid;
        else
            first = mid + 1;
    }

    return first; /* or last */
}
    InformationsquelleAutor jfly
  3. 2

    Nur für die längste zunehmende sub-Sequenz-Algorithmus geordnete paar (A[i], i), durch die Verwendung einer lexikographischen vergleichen.

    InformationsquelleAutor Ukkonen
  4. 1

    Eine ganz andere Lösung für dieses problem ist die folgende. Machen Sie eine Kopie des Arrays und sortiert werden. Dann berechnen Sie den minimalen Wert ungleich null Unterschied zwischen zwei Elementen des Arrays (das wird der minimale Wert ungleich null Unterschied zwischen zwei benachbarte array-Elemente) und nennen es δ. Dieser Schritt braucht Zeit O(n log n).

    Die wichtige Beobachtung ist, dass, wenn Sie hinzufügen 0-element 0 des ursprünglichen Arrays, δ/n, um das zweite element des ursprünglichen Arrays, 2δ/n, um das Dritte element des Arrays, etc., dann ist jede nondecreasing Sequenz in das original-array wird eine streng monoton wachsende Folge in das neue array und Umgekehrt. Deshalb verwandeln Sie das array auf diese Weise, dann führen Sie ein standard längsten steigenden Teilfolge solver, die läuft in Zeit O(n log n). Das Ergebnis dieses Prozesses ist eine O(n log n) Algorithmus für das finden der längsten nondecreasing Teilfolge.

    Betrachten Sie zum Beispiel 30, 20, 20, 10, 10, 10, 10. In diesem Fall δ = 10 und n = 7, δ /n ≈ 1.42. Das neue array wird dann

    40, 21.42, 22.84, 14.28, 15.71, 17.14, 18.57

    Hier, die führt 14.28, 15.71, 17.14, 18.57, die Karten zurück zu 10, 10, 10, 10 in das ursprüngliche array.

    Hoffe, das hilft!

    InformationsquelleAutor templatetypedef
  5. 0

    Meine Java-version:

      public static int longestNondecreasingSubsequenceLength(List<Integer> A) {
    int n = A.size();
    int dp[] = new int[n];
    int max = 0;
    for(int i = 0; i < n; i++) {
        int el = A.get(i);
        int idx = Arrays.binarySearch(dp, 0, max, el);
        if(idx < 0) {
            idx = -(idx + 1);
        }
        if(dp[idx] == el) { //duplicate found, let's find the last one 
            idx = Arrays.binarySearch(dp, 0, max, el + 1);
            if(idx < 0) {
                idx = -(idx + 1);
            }
        }
        dp[idx] = el;
        if(idx == max) {
            max++;
        }
    }
    return max;
}
    InformationsquelleAutor boneash
Schreibe einen Kommentar