Fog Creek Software
Discussion Board




Longest Monotone Subsequence

A topic that seems popular this season: Given an array of numbers, find the longest subsequence whose elements grow monotonically:
  1 4 8 2 5 7 3 6 => 1 4 5 7
  1 4 8 2 5 7 3 6 7 => 1 4 5 6 7
  1 4 8 2 3 7 4 6 => 1 2 3 4 6

I'm giving my solution in hopes people will comment on it; feel free not to look at it until you solve it yourself :)

int maxRank (int curr, int* arr, int* rank) {
    int max = 0 ;
    for (int i = 1; i < curr; ++i) {
        if (arr[i]<arr[curr] && rank[i]>rank[max]) {
            max = i ;
        }
    }

    return max ;
}

void printReverse (int curr, int* arr, int* back) {
    if (curr == 0) return ;
    printReverse (back[curr], arr, back) ;
    cout << arr[curr] << " " ;
}

void longestMonotoneSubsequence (int count, int* arr) {
    int* back = new int[count] ;
    int* rank = new int[count] ;
    int max = 0 ;
    rank[0] = 0, back[0] = 0 ;
    for (int i = 1; i < count; ++i) {
        back[i] = maxRank (i, arr, rank) ;
        rank[i] = rank[back[i]]+1 ;
        if (rank[i] > rank[max]) {
            max = i ;
        }
    }

    printReverse (max, arr, back) ;
    cout << "\n" ;
    delete rank, back ;
}

I've seen it before (prob in Knuth), but the key insight for me this time was realizing that we can be greedy as long as we search in parallel.

[printReverse is just an illustration of how to reconstruct the answer from the set of back pointers.]

Kartik Agaram
Monday, March 14, 2005

Looks like your algorithm is O(n^2). There is an O(nlogn) algorithm for this.

Tapori
Thursday, March 17, 2005

Ah.

And I just realized that this forum is connected to a website with interview questions. I apologize if I was breaking protocol by posting my own questions.

Kartik
Thursday, March 17, 2005

Don't worry about it. The questions on the site seems to have been stagnant for months now. Any new puzzle is welcome :-)

Tapori
Sunday, March 20, 2005

How do you get the O(nlogn) solution, by storing the traversed elements in binary tree or something.

Binary tree is not giving O(nlogn). Is there anyother approach?


Thanks

Anonymous and I dont know why
Monday, March 21, 2005

Anonymous,

Say the sequence is A[1], A[2], ... A[n]. (Assume all are distinct).

A well known algorithm is to find, for each possible length k, the smallest number in the sequence, say s_k such that max length monotonic subsequence ending at s_k has length k. An important property of these s_i's is that s_1 < s_2 < s_3 ... (why?)


We have the above list of s_i's maintained for the sequence A[1]... A[n-1].

Now we consider A[n].
Find where A[n] lies in s_1, s_2, ..., s_r (r is the max length possible in A[1], ..., A[n-1]).
If A[n] > s_r,  set s_(r+1) = A[n].
If A[n] < s_1, set s_1 = A[n]

else find j such that s_j < A[n] < s_(j+1)
set s_(j+1) = A[n].


The look up in the s_i and insertion can be done in O(log r) time using a balanced binary tree.

Thus starting from A[1] and looking at A[2], A[3].... A[n] we take no more than O(n logn) time.

This algorithm gives us the length of the longest monotonic subsequence and can easily be modified to get the actual subsequence itself.

Tapori
Tuesday, March 22, 2005

*  Recent Topics

*  Fog Creek Home