For example in the following array

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

{1,2,5}

{1,2,7}

{1,2,9}

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.

` `

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.