Sunday, December 18, 2011

Longest increasing subsequence

December 18, 2011  , , , , ,  No comments

Longest Increasing Subsequence has been a classic Dynamic Programming problem. O(N^2) has been around for a while but more interesting is the following O(n log n) solution.

Problem 
Input : Sequence of integers (or any comparable items)
Output : Longest increasing subsequence of the sequence, which may not be contiguous.

For example : We have sequence : 1,8,2,7,3,6,4,5 which has the longest increasing subsequence : 1,2,3,4,5.

Note that the numbers are non-contiguous.

Solution 1 - Brute Force
 You can hear the video directly here - (source). Meanwhile I am writing it out here.
Input = {2 , 7, 3, 4, 9, 8, 12}
Output = { 2, 3, 4, 9, 12} OR {2,3,4,8,12}

We can create 2n sets if the array size is n and check the longest size.But time complexity is O(2n).

Solution 2 - Using DP
 Now lets take a bottom up approach

Let LS(i) = longest increasing sequence till element A[i], where A is the sequence

Lets say that array is 2 7 3 4 9 8 12. Now lets try to find the optimal substructure.

i starts from 1 (rather than 0)

LS(1) = 2
LS(2) = 2 7
LS(3) = 2 3 OR 2 7
LS(4) = 2 3 4
LS(5) = 2 3 4

Case 1 -element A[i] is included. eg i = 4, element 4.
In this case, elements before should be less than 4, so the elements that can be included are 2 and 3, LIS = 3 as now we have 3 elements (2,3,4). We already know LS(2) and as A[2] = 3, < 4, we add 4 to that subsequence

Case 2 : element A[i] is not included
Now suppose we have i = 5, A[i] = 9. Now we have to find LIS before it, till i-1, such that  A[i]>A[j], where j < i. We find that we have 2 subsequence - 2,3,4 and 2,7. We can add 9 to any of these, but we pick (2,3,4) as it is already longer, we will get sequence more better.

Here we can include 4, if we select subsequence as ( 2, 3), but if we select subsequence (2,7) we cannot.



LS(i) = MAX (LS(j) + 1) , where we have j such that 1<j<i and A[i]>A[j]
                      OR
            1 if no such j exists

Example 
Consider the example array - 10,22,9,33,21,50,41,60,80
A[1] = 10 , LS(1) = 1, IF we have only 1 element 10, then LIS has only 1 element.
A[2] = 22 , LS(2) = 1 + 1 = 2, as 10 and 22 can be part of LIS
A[3] = 9  , LS(3) = 1 + max(LS(j)+1), but no such LS(j) exists such that, A[3]>A[j], so max(LS(j))+1 cancels out, and LS(3)  = 1
So, LS(3) = 1

A[4] = 33 , LS(4) = 1 + max(1,2,1) = 3 as all 10, 22 and 9 are less than 33.
A[5] = 21 , LS(5) = 1 + max(1,1) = 2 as both 10 and 9 are less
A[6] = 50 , LS(6) = 1 + max(1,2,1,3,2,1) = 4 as all elements are less than 50
A[7] = 41 , LS(7) = 1 max(1,2,1,3,2) = 4 (max taken from 33)
A[8] = 60 , LS(8) = 1 max(1,2,1,3,) = 5 (max taken from 33)
A[9] = 80 , LS(7) = 1 max  = 1+5 = 6 (max taken from 33)

So, the algorithm tells us that max length of LIS is 6.

Here is pseudo-code: 
int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i++)
{
   DP[i] = 1;
   prev[i] = -1;

   for (int j = i - 1; j >= 0; j--)
      if (DP[j] + 1 > DP[i] && array[j] < array[i])
      {
         DP[i] = DP[j] + 1;
         prev[i] = j;
      }

   if (DP[i] > maxLength)
   {
      bestEnd = i;
      maxLength = DP[i];
   }
}


Time Complexity - O(n2)

Here is the code in java:

public class LIS {
  public static void main(String[] args) {
        //let's use the example discussed in slides
        int[] nums = {2,6,4,5,1,3};
        printLIS(nums);
  }
  //define the key method to print longest increasing subsequence
  public static void printLIS(int[] nums) {
        //as we discussed in slides, in order to use DP in this example, we need
        //1. a size array to keep track of longest LIS ending with current position
        //2. an accordingly string array to keep track of the path for printing out
        String[] paths = new String[nums.length];
        int[] sizes = new int[nums.length];
        
        //firstly we assign the intial values to each path/size, by setting size
        //to 1 and path equals the value (that means initially each path starting/ending
        //with its current position
        for(int i=0; i<nums.length; i++) {
             sizes[i] = 1;
             paths[i] = nums[i] + " ";//we add a space for separation
        }
        
        //before we start the loop, 
        //we define a support variable called maxLength to keep track
        int maxLength = 1;//notice it is 1, but it really does not matter if sets to 0
        
        for(int i=1; i<nums.length; i++) { 
          //notice we start from 2nd postion, 1st position is no point
             for(int j=0; j<i; j++) { //the inner loop is to check all previous items!
                  //now it's the key step, 
              //when do we append our current index to the previous subsequence?
                  //it has to meet 2 requirements, 
              //current>previous ending and size is increasing!
                  if(nums[i]>nums[j] && sizes[i] < sizes[j]+1) { //notice plus one!!
                        //if so, we need update sizes and path
                        sizes[i] = sizes[j]+1;
                        paths[i] = paths[j] + nums[i] + " ";//append current values to end!
                        //also update the maxLength if necessary
                        if(maxLength < sizes[i])
                             maxLength = sizes[i];
                  }
             }
        }
        
        //finally go scanning the size array again and print out the path when size matches
        for(int i=1; i<nums.length; i++) {
             if(sizes[i] == maxLength)
                  System.out.println("LIS: "+paths[i]);
        }
        //please notice we did not break whenever a max length found, 
        //because it may not be the only one longest increasing subsequence. 
        //The only definitive thing is the length of LIS, btw.
  }
}


Now lets move to O(n log n) solution.

Solution 3 : Using Binary Search
We will build the O(N log N) idea on the previous one. The essential improvement in this algorithm happens in the second "for" loop. Instead of scanning linearly through all jbinary search.

Suppose we are at point i and we want to know the length of longest increasing subsequence ending at A[i]. So, can this length  be greater than i (1<=i<=n)? Certainly not, because a subsequence cannot be longer than its parent sequence.
Which means this length, lets call it LIS[i], must be between 1 - i inclusive.

Now we introduced a new array, c[], which is pretty ambitious by definition but, as we will see, builds naturally without any extra computation.

We define c[i] : smallest end-element of an i-length increasing subsequence of original sequence.

 Understanding c[i] - 
First of all, we won't need to build it separately; it will get build up itself. With that burden off, lets first try to understand what it says. It says that, suppose our sequence, A, has multiple (increasing) subsequences of length i. Then, take all those subsequences, and find minimum of their last elements and that is c[i].
Also, if there is an increasing subsequence of length i, there will always be at least 1 subsequence of lengths less than i.

Using the hard work i.e. c[i] - 
How can we use c[i] to solve our original problem? Suppose that we have solved that LIS problem for A[1...n] and built the c[k] array. So now, we know the following -


  • LIS of A[1...n] is l.
  • c is l length long.
  • c[1] is the minimum element of A, since 1-length subsequence is the element itself.
  • c[k] <= c[k+1] for every k. This is because, say c[k] > c[k+1], this means that there exist an k-LIS(of form ****c[k]) and (k+1)-LIS(of form ****Rc[k+1]) such that their ending is minimum of their class, and c[k] > c[k+1]. Let the element just before c[k+1] in (k+1)-LIS be R. Then R<=c[k+1]<=c[k]. Which means first k-of (k+1)-LIS ending at R is a k-LIS with the ending element, R smaller than c[k] - contradiction.
  • Above point signifies that c is sorted in increasing order.
Now, suppose we were to add (n+1)th element to A. How much time it will take to update c?
  • Since after updating c, it should remain sorted, therefore we can find the place A[n+1] will take in c[] using binary search.
  • Say we find a j, such that c[j] <= A[n+1] <= c[j+1]. This means, we can replace c[j+1] with A[n+1] and still have a (j+1)-LIS ending at A[n+1] which is smaller than its previous contender, and c is still sorted.
  • Say c[l] <= A[n+1]. This means there exists a l-length subsequence ending with c[l], and by appending A[n+1] to it, we can get a bigger (l+1)-LIS. 
  • Say c[1] >= A[n+1]. This means current element is the new minimum and we can replace c[1] by this.
All in all, updating c[] on addition of a new element to A takes O(log N) time. This is essentially the algorithm, the improvement or the magic of reducing the inner "for loop" of O(N2) approach.

The delirium

You can find many resources in internet explaining this algorithm in more detail. The Wikipedia page contains an extension of this that enables one to actually print the LIS and not just the length of LIS (which is basically by storing index of number in c[] rather than the number itself, and maintaining a Parent[] array to keep track).
What got me confusing on reading the Wikipedia page was the direct implementation of method without explaining the actual "improvement" in detail. The confusion arises mainly because there doesn't appear any direct reason why above should work. In fact, if you don't know it, it's unlikely you'd come up with this approach on your own.
The key to confusion is this line - minimum of all i-length LIS endings. It's just too much information crammed into a sentence. And before you even swallow it, the Wikipedia article makes it worse by introducing Parent array and starts using pointers (what the hell is A[M[P[i]]] ??? :)). Okay, may be I'm going too much against it; in fact it's the most generic implementation you'd end up using, but it's still not suitable for understanding for newbies.
The key to understanding it is this - these terms were not thought before the discovery of the algorithm, but only after, so that something tangible can be said to describe c.

The discovery of the algorithm, or as I'd like to put, discovery of c came through a very simple observation. Consider any Increasing Subsequence of A, say A[i1],A[i2],...A[ik]. This is a sorted sequence of length k and we can also find a sorted sequence of length Now, we come across a new element, say x, and we'd like to know how to extend existing Increasing sequence by using this x.
Initially we'd like to check if x can be appended to the existing LIS by comparing A[ik] with x. This is exactly the theme of O(n2) approach. If it's bigger, then we can safely append it to the LIS and get a new LIS. If however, we weren't so lucky, we would abort and look at other Increasing Sub-sequences.

The improved approach is a little more hardy and doesn't quit on failure. If the ending of our Increasing Sub-sequence is more than x, we still try to find a point in the Increasing Sub-sequence that's smaller than x.

What do we gain from it? Well, to start with, we will find another sequence of some length <=k that's an Increasing Sub-sequence of A. Moreover, if we replaced the point just greater than x in this Increasing Sub-sequence, it will remain sorted, only that it will be a Sub-sequence of A up to x (since replacing will break the order of elements). 

 c = {A[i1],A[i2],...,x}, ...  , A[ik]

 The above process ensure that c[i] has ending of an Increasing Sub-sequence of length i and that it's smallest such ending. Now see - we arrived at the definition from the process, not the other way. Moreover, keeping the smallest ending enables us to check whether a new element can extend an existing Increasing Sub-sequence.

Because, if a new element x were to form a Increasing subsequence of length p+1, it is easier to check if there exists an Increasing Sub-sequence of length p, by checking the smallest ending element of all such Sub-sequences of length p.

And since the list above, c never gets shorter but only longer, if at all, we are guaranteed to find LIS by above method.

Also, note that it's an online approach - a stream of numbers can be used as input.


References - 










0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)