Longest increasing subsequence (LIS) problem is to find the length of longest subsequnce out of a given sequnce such that all the element of the subsequence is sorted in strictly increasing order of their value.
INPUT SPECIFICATION
An array (may be unsorted)
OUTPUT SPECIFICATION:
Length of LIS
Examples:
Input Array 10,22,9,33,21,50,41,60,80
Length of LIS is 6 & LIS is 10,22,33,50,60,80
Input Array 1,2,3,4,5,6,7,8,7,6,5,4,5,6,7,8,9,10,11
Length of LIS is 11 & LIS is 1,2,3,4,5,6,7,8,9,10,11
import java.io.*;
import java.util.*;
public class ArraySubsequence {
public static void main(String[] args) {
int n;
int[] arr;
Scanner in = new Scanner(System.in);
System.out.println("Enter the size of the array:");
n = in.nextInt();
arr = new int[n];
System.out.println("Enter the elements of the array:");
for(int i = 0; i < n; i++)
arr[i] = in.nextInt();
LIS ls = new LIS();
ls.lisGenerate(arr);
}
}
class LIS {
public void lisGenerate(int[] seq) {
int[]L=new int[seq.length];
L[0]=1;
for(int i=1;i<L.length;i++) {
int maxn=0;
for(int j=0;j<i;j++){
if(seq[j]<seq[i]&&L[j]>maxn){
maxn=L[j];
}
}
L[i]=maxn+1;
}
int maxi=0;
for(int i=0;i<L.length;i++) {
if(L[i]>maxi) {
maxi=L[i];
}
}
System.out.println(maxi);
}
}
