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

Answer 2

Your code nearly works except a problem in your binary_search() function, this function should return the index of the first element that's greater than the target element(x) since you want the longest non-decreasing sequence. Modify it to this, it'll be OK.

If you use c++, std::lower_bound() and std::upper_bound() will help you get rid of this confusing problem. By the way, the if statement"if (height[s[k]] >= height[i])" is superfluous.

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 */
}

Answer 3

Just apply the longest increasing sub-sequence algorithm to ordered pair (A[i], i), by using a lexicographic compare.

Answer 4

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

Answer 5

A completely different solution to this problem is the following. Make a copy of the array and sort it. Then, compute the minimum nonzero difference between any two elements of the array (this will be the minimum nonzero difference between two adjacent array elements) and call it δ. This step takes time O(n log n).

The key observation is that if you add 0 to element 0 of the original array, δ/n to the second element of the original array, 2δ/n to the third element of the array, etc., then any nondecreasing sequence in the original array becomes a strictly increasing sequence in the new array and vice-versa. Therefore, you can transform the array this way, then run a standard longest increasing subsequence solver, which runs in time O(n log n). The net result of this process is an O(n log n) algorithm for finding the longest nondecreasing subsequence.

For example, consider 30, 20, 20, 10, 10, 10, 10. In this case δ = 10 and n = 7, so δ / n ≈ 1.42. The new array is then

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

Here, the LIS is 14.28, 15.71, 17.14, 18.57, which maps back to 10, 10, 10, 10 in the original array.

Hope this helps!

Answer 6

I have my simple solution for the longest non-decreasing subsequence using upper bound function in c++. Time complexity (nlogn)

int longest(vector<long long> a) {
    vector<long long> s;
    s.push_back(a[0]);
    int n = a.size();
    int len = 1;
    for (int i = 1; i < n; i++) {
        int idx = upper_bound(s.begin(), s.end(), a[i]) - s.begin();
        int m = s.size();
        if (m > idx) {
            s[idx] = a[i];
        } else {
            s.push_back(a[i]);
        }
    }
    return s.size();
}

Answer 7

If you know the algorithm for LIS, then changing inequalities in the code, gives the Longest Non-Decreasing subsequence.

Code for LIS:

public int ceilIndex(int []a, int n, int t[], int ele){
    int l=-1, r=n+1;
    while(r-l>1){
        int mid=l+(r-l)/2;
        if(a[t[mid]]<ele) l=mid;
        else r=mid;
    }
    return r;
}

public int lengthOfLIS(int[] a) {
    int n=a.length;
    int index[]=new int[n];
    int len=0;
    index[len]=0;
    int reversePath[]=new int[n];
    for(int i=0;i<n;i++) reversePath[i]=-1;
    for(int i=1;i<n;i++){
        if(a[index[0]]>=a[i]){
            index[0]=i;
            reversePath[i]=-1;
        }else if(a[index[len]]<a[i]){
            reversePath[i]=index[len];
            len++;
            index[len]=i;
        }else{
            int idx=ceilIndex(a, len, index, a[i]);
            reversePath[i]=index[idx-1];
            index[idx]=i;
        }
    }
    for(int i=0;i<n;i++) System.out.print(reversePath[i]+" ");
    System.out.println();
    // printing the LIS in reverseFashion
    // we iterate the indexes in reverse
    int idx=index[len];
    while(idx!=-1){
        System.out.print(a[idx]+" ");
        idx=reversePath[idx];
    }
    return len+1;
}

Code for Longest Non-Decreasing subsequence:

public int ceilIndex(int []a, int n, int t[], int ele){
    int l=-1, r=n+1;
    while(r-l>1){
        int mid=l+(r-l)/2;
        if(a[t[mid]]<=ele) l=mid;
        else r=mid;
    }
    return r;
}

public int lengthOfLongestNonDecreasingSubsequence(int[] a) {
    int n=a.length;
    int index[]=new int[n];
    int len=0;
    index[len]=0;
    int reversePath[]=new int[n];
    for(int i=0;i<n;i++) reversePath[i]=-1;
    for(int i=1;i<n;i++){
        if(a[index[0]]>a[i]){
            index[0]=i;
            reversePath[i]=-1;
        }else if(a[index[len]]<=a[i]){
            reversePath[i]=index[len];
            len++;
            index[len]=i;
        }else{
            int idx=ceilIndex(a, len, index, a[i]);
            reversePath[i]=index[idx-1];
            index[idx]=i;
        }
    }
    for(int i=0;i<n;i++) System.out.print(reversePath[i]+" ");
    System.out.println();
    // printing the LIS in reverseFashion
    // we iterate the indexes in reverse
    int idx=index[len];
    while(idx!=-1){
        System.out.print(a[idx]+" ");
        idx=reversePath[idx];
    }
    return len+1;
}