Problem #Longest Increasing Sequence

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 :

&nbsp;
<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. 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s