Longest Increasing Subsequence problem

Given an array of numbers, we have to find the longest sub sequence of that array which is strictly increasing.

For example in the following array

[8 1 4 2 7 9 5]

{8,9}
{1,4,7,9}
{1,2,7,9}
{1,2,5}
{1,2,7}
{1,2,9}

are some of the increasing sub-sequences. The second and third are the longest increasing sub sequences with length 4. Our job is to find the length of the longest increasing sub sequence.
There are various ways of solving this problem. In this post we will use the following algorithm to find the length of the longest increasing sub sequence.

We take one by one element from the array and insert them into a sorted set data structure. (TreeSet class in Java is one such implementation of sorted set. Please see the program details below)
Once the element is inserted, we will see if it is appended at the end. If it is, we proceed to the next element in the array. If it is not, we will delete the next element to newly inserted element.
At the end, the size of the sorted set is the length of the longest increasing sub sequence.

To understand this further, let us look at the contents of the sorted set in each iteration

Iteration 1: {8} – element added at the end
Iteration 2: {1} – 1 added before 8, so 8 got deleted
Iteration 3: {1,4} – 4 added at the end
Iteration 4: {1,2} – 2 added before 4, 4 got deleted
Iteration 5: {1,2,7} – 7 added at the end
Iteration 6: {1,2,7,9} – 9 added at the end
Iteration 7: {1,2,5,9} – 5 added before 7, 7 got deleted

So the size{1,2,5,9} = 4 is the required answer. However, the sequence may not reflect the longest sequence. It will only indicate the length of it.

The following Java program implements the above algorithm. In this program you can see how the TreeSet data struture is used. This data structure maintains the sorted order when the elements are inserted. It does not allow duplicates to be inserted. The add() method inserts the element if there is no such element exists in the set and it returns true if the element is newly added, otherwise it returns false.

The last() method returns the last element in the set. The higher() method returns the least element which is greater than the given element. All these methods are used in the following program.

import java.util.TreeSet;

public class LIS {
    public static void main(String[] args)
    {
        Test1();
        Test2();
        Test3();
        Test4();
        Test5();
    }
    public static void Test1()
    {
        int [] array = {8,1,4,2,7,9,5};
        System.out.println("LIS{8,1,4,2,7,9,5}: " + getLengthOfLIS(array));
    }
    public static void Test2()
    {
        int [] array = {1};
        System.out.println("LIS{1}: " + getLengthOfLIS(array));
    }
    public static void Test3()
    {
        int [] array = {2,1};
        System.out.println("LIS{2,1}: " + getLengthOfLIS(array));
    }
    public static void Test4()
    {
        int [] array = {1,2,3,4,5};
        System.out.println("LIS{1,2,3,4,5}: " + getLengthOfLIS(array));
    }
    public static void Test5()
    {
        int [] array = {5,4,3,2,1};
        System.out.println("LIS{5,4,3,2,1}: " + getLengthOfLIS(array));
    }
    public static int getLengthOfLIS(int[] array)
    {
        TreeSet<Integer> s = new TreeSet<Integer>();
        for( int i = 0 ; i < array.length ; i++)
        {
           //if array[i] is newly added?
           if( s.add(array[i]) )
           {
               //if array[i] is not the last element?
               if( array[i] != s.last() )
               {
                    //remove it's next element; s.higher() gives the least element 
                   //which is greater than array[i]
                   s.remove(s.higher(array[i]));
               }
           }
        }
        return s.size();
    }
}

~~This method runs in linear time (O(n)) and O(n) extra space for the sorted set.~~

Leave a Reply Cancel reply