Longest Increasing Subsequence O(n logn)

Given an array of integers, find the longest increasing subsequence.
Example: X = {3,1,5,2,6,4,9} LIS(X) = {1,2,4,9}

Please check out the video which explains the solution to this problem.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm Visualization




Code Snippet

			
package com.ideserve.virendra.questions;

public class LongestIncreasingSubsequence {
	
	public static void LIS(int X[])
	{
		int parent[]= new int[X.length]; //Tracking the predecessors/parents of elements of each subsequence.
		int increasingSub[]= new int[X.length + 1]; //Tracking ends of each increasing subsequence.
		int length = 0; //Length of longest subsequence.
		
		for(int i=0; i<X.length; i++)
		{
			//Binary search
			int low = 1;
			int high = length;
			while(low <= high)
			{
				int mid = (int) Math.ceil((low + high)/2);
				
				if(X[increasingSub[mid]] < X[i])
					low = mid + 1;
				else
					high = mid - 1;
			}
			
			int pos = low;
			//update parent/previous element for LIS
			parent[i] = increasingSub[pos-1];
			//Replace or append
			increasingSub[pos] =  i;
			
			//Update the length of the longest subsequence.
			if(pos > length)
				length=pos;
		}
		
		//Generate LIS by traversing parent array
		int LIS[] = new int[length];
		int k 	= increasingSub[length];
		for(int j=length-1; j>=0; j--)
		{
			LIS[j] =  X[k];
			k = parent[k];
		}
		
		
		for(int i=0; i<length; i++)
		{
			System.out.println(LIS[i]);
		}
	
		
	}
	
	public static void main(String args[])
	{
		int X[] = {3,1,5,0,6,4,9};
		LIS(X);
	}
}
		

Order of the Algorithm

Time Complexity is O(nlog n)
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.

    Virendra Karappa

    Ninja Programmer