Find Longest Increasing Subsequence Using Binary Search

In this approach we will find longest increasing Subsequence using Binary Search. Time Complexity for this approach will be nlogn.

The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in strictly ascending order. This is called the Longest Increasing Subsequence (LIS) problem.

public class LongestIncreasingSubsequenceBinarySearch {

	public static void main(String[] args) {
		int[] arr = new int[] {3, 4, -1, 5, 8, 2, 3, 12, 7, 9, 10};
		int[] tempArr = new int[arr.length];
		int[] resArr = new int[arr.length];
		int len=0;
		int tempArrLastIndex = 0;
		
		for(int i=0;i<arr.length;i++) {
			resArr[i]=-1;
		}
		
		for(int i=0;i<arr.length-1;i++) {
			if(arr[i+1]>arr[tempArr[tempArrLastIndex]]) {
				tempArrLastIndex++;
				tempArr[tempArrLastIndex]=i+1;
				len++;
				resArr[i+1]=tempArr[tempArrLastIndex-1];
			}
			else {
				for(int j=0;j<=tempArrLastIndex;j++) {
					if(arr[i+1]<arr[tempArr[j]]) {
						tempArr[j]=i+1;
						if(j==0)
							resArr[i+1]=0;
						else
							resArr[i+1]=tempArr[j-1];
						break;
					}
				}
			}
		}
		
		System.out.println("Increasing Subsequence : " + (len+1));
		int i = tempArr[tempArrLastIndex];
		while(resArr[i] != -1)
		{
			System.out.println(arr[i]);
			i = resArr[i];
		}

	}

}