DP--Longest Increasing Subsequence

[NewOne]

Hey all,

This time I need some help about the famous LIS problem.. Well, I found an algorithm that finds the LIS, but don't know how to procede to reconstruct the subsequence. Here is the code :

[c]
#include <stdio.h>
#include <iostream.h>
#include <conio.h>

void main()
{
int height[10];
int length[10];
int predecessor[10];
clrscr();

for(int i=1;i<6;i++)
{
printf("height[%d]: ",i);
cin>>height;
// initialising
length=1;
predecessor=0;
}

for(i=1;i<5;i++)
for(int j=i+1;j<6;j++)
if(height[j]>height)
if (length+1 > length[j])
{
length[j] = length + 1;
predecessor[j] = i;

}


return;
}[/c]

I ran it with the example : height : 1,6,2,3,5

At the end of the loop :
length: [1,2,2,3,4], because 5 > 3
predecessor: [nil,1,1,3,4]

The problem now is how to refind the LIS (in this example : 1,2,3,5)
If you could help, it just would be very nice:)

[kmhasan]

made a few changes to your code. you'd find the printPath method printing the longest increasing sequence. if you'd tweak it a bit, i think you can print all longest increasing sequences...
[c]
#include <stdio.h>

#define MAXN 1000

int height[MAXN];
int length[MAXN];
int predecessor[MAXN];
int N;

/* recursively prints the LIS */
void printPath(int index) {
if (predecessor[index]==0) {
printf("%d",height[index]);
return;
}
printPath(predecessor[index]);
printf(",%d",height[index]);
}

int main() {
int i, j, maxindex;
scanf("%d",&N); /* number of items */
for(i=1;i<=N;i++) {
scanf("%d",&height); /* length=1 is not needed */
predecessor=0;
}

maxindex = 0;
length[maxindex] = 0;
for (i=1; i<=N; i++) {
int maxlength = 0;
int parent = 0;
for (j=i-1; j>0; j--)
if (height>height[j] && length[j]>maxlength) {
maxlength = length[j];
parent = j;
}
length = maxlength + 1; /* +1 as the i th item itself gets added to the seq */
predecessor = parent;

if (length>length[maxindex])
maxindex = i;
}
printf("Length of LIS: %d\n",length[maxindex]);
printPath(maxindex); /* print the LIS */
printf("\n");
return 0;
}
[/c]

[NewOne]

Hi,

I modified my source code by using your fucntion (that prints the LIS).
Here is the new code :

[c]#include <stdio.h>
#include <iostream.h>
#include <conio.h>
#define NMAX 100

int N; //sequence length
int height[NMAX];
int length[NAMAX];
int predecessor[NMAX];

int maxarr(int t[],int n) //simply returns the maxindex of an array of size N
{
j=1,max=t[1];
for(int i=1;i<=n;i++)
if(t>max)
{
max=t;
j=i;
}
return j;
}


void printPath(int index) //Your function that prints the LIS
{
if (predecessor[index]==0)
{
printf("%d",height[index]);
return;
}
printPath(predecessor[index]);
printf(",%d",height[index]);
}

main()
{
clrscr();
cout<<"Length : ";
cin>>N;

for(int i=1;i<=N;i++)
{
printf("height[%d]: ",i);
cin>>height;
// initialising
length=1;
predecessor=0;
}

for(i=1;i<=N-1;i++)
{
for(int j=i+1;j<=N;j++)
if(height[j]>height)
if (length+1 > length[j])
{
length[j] = length + 1;
predecessor[j] = i;

}

printf("\n");
}


printf("Length of LIS: %d\n",length[maxarr(length,N)]);
printPath(maxarr(length,N)); /* print the LIS */
printf("\n");
getch();


return 1;
}[/c]

But the problem is that I need to understand the algorithm good enough to be able to modify it (sur mesure)..
Thanks!
----------
PS. This program doesn't do exactly the same as the previous, that's because predecessor[] is not filled the same way.. But they both do give a right solution!