In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. [Wikipedia] I recently got this problem to solve in techgig. I wrote the code and as per my understanding it is giving the correct solution. But unfortunately, the website shows its not a correct answer. 😦

Thought of sharing the same so that you guys can correct me if wrong.</span>

So, what is longest increasing sequence or LIS problem all about.

Suppose, I take an array of 9 numbers as :

Enter array size:9

enter 1:

10

enter 2:

22

enter 3:

9

enter 4:

33

enter 5:

21

enter 6:

50

enter 7:

41

enter 8:

60

enter 9:

80

Now the array sequences will be:

Array1:{10,22,33,50,60,80}

Array2:{22,33,50,60,80}

Array3:{9,33,50,60,80}

Array4:{33,50,60,80}

Array5:{21,50,60,80}

Array6:{50,60,80}

Array7:{41,60,80}

Array8: {60,80}

Out of these the longest sequence is {10,22,33,50,60,80} with the size of 6. Correct isn’t it ?

So I wrote the code accordingly as :

<code>

int array[]=new int[size];

int lis[][]=new int[size][size];

for (int i = 0; i < array.length; i++) {

System.out.println(“enter “+(i+1)+”:”);

array[i]=Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());

}

int i=0;

int count=0,index=0;

while(i<size-1)

{

int j=0;

int k=0;

lis[i][k]=array[i];

j=i;

while (j<size-1) {

if(lis[i][k]< array[++j])

{

lis[i][++k]=array[j];

}

}

System.out.print(“Array”+i+”:”);

for (int k2 = 0; k2 <=k; k2++) {

System.out.print(lis[i][k2]+”,”);

}

if (count<k) {

count=k;

index=i;

}

System.out.println(“”);

i++;

}

System.out.println(“Largest array:size “+(count+1));

for (int j = 0; j <=count; j++) {

System.out.print(lis[index][j]+”,”);

}

</code>

where array[] is the input for the problem and lis[][] are the respective array sequences.

Run the code with various outputs. It should give correct results. 🙂