longest nondecreasing subsequence in O(nlgn)

Question

I have the following algorithm which works well

I tried explaining it here for myself http://nemo.la/?p=943 and it is explained here http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ as well and on stackoverflow as well

I want to modify it to produce the longest non-monotonically increasing subsequence

for the sequence 30 20 20 10 10 10 10

the answer should be 4: "10 10 10 10"

But the with nlgn version of the algorithm it isn't working. Initializing s to contain the first element "30" and starting at the second element = 20. This is what happens:

1. The first step: 30 is not greater than or equal to 20. We find the smallest element greater than 20. The new s becomes "20"

2. The second step: 20 is greater than or equal to 20. We extend the sequence and s now contains "20 20"

3. The third step: 10 is not greater than or equal to 20. We find the smallest element greater than 10 which is "20". The new s becomes "10 20"

and s will never grow after that and the algorithm will return 2 instead of 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;
}

Answer 1

To find the longest non-strictly increasing subsequence, change these conditions:

1. If A[i] is smallest among all end candidates of active lists, we will start new active list of length 1.
2. If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].
3. If A[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.

to:

1. If A[i] is smaller than the smallest of all end candidates of active lists, we will start new active list of length 1.
2. If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].
3. If A[i] is in between, we will find a list with largest end element that is smaller than or equal to A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.

The fourth step for your example sequence should be:

10 is not less than 10 (the smallest element). We find the largest element that is smaller than or equal to 10 (that would be s[0]==10). Clone and extend this list by 10. Discard the existing list of length 2. The new s becomes {10 10}.