Ich habe den folgenden Algorithmus, der gut funktioniert

Ich habe versucht, es hier für mich selbst zu erklärenhttp://nemo.la/?p=943 und es wird hier erklärthttp://www.geeksforgeeks.org/längste-monotonisch- ansteigende-Subsequenz-Größe-n-Log-n/ sowie auf Stackoverflow als auch

Ich möchte es modifizieren, um die längste nicht monoton ansteigende Folge zu erzeugen

für die Sequenz 30 20 20 10 10 10 10

Die Antwort sollte 4 sein: "10 10 10 10"

Aber die mit nlgn-Version des Algorithmus funktioniert nicht. Initialisieren von s, um das erste Element "30" zu enthalten und mit dem zweiten Element zu beginnen = 20. Dies ist, was passiert:

Der erste Schritt: 30 ist nicht größer als oder gleich 20. Wir finden das kleinste Element größer als 20. Das neue s wird zu "20"

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

Der dritte Schritt: 10 ist nicht größer als oder gleich 20. Wir finden das kleinste Element größer als 10, das "20" ist. Das neue s wird "10 20"

Danach wächst s nie mehr und der Algorithmus gibt 2 statt 4 zurück

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;
}