ritesh_NITW - 6 months ago 50

C++ Question

I was trying a problem on SPOJ,in which we have to simply find the Length of Longest Increasing Sub-sequence of the given Array A.

I had solved this problem using a dynamic programming O(n^2)algorithm and the solution got accepted..Here is the code,that got Accepted:

`void LIS(int *A,int A_Length)`

{

int Seq[MAX];

for(int i=0;i<A_Length;++i)

{

int maxima=0;

for(int j=0;j<i;++j)

{

if(A[i]>A[j])

{

maxima=max(Seq[j],maxima);

}

}

Seq[i]=maxima+1;

//cout<<Seq[i]<<endl;

}

cout<<*max_element(Seq,Seq+A_Length)<<endl;

}

But When i tried to solve it using the Second Method (LINK),which is ::

`A simple way of finding the longest increasing subsequence is`

to use the Longest Common Subsequence (Dynamic Programming) algorithm.

[1]Make a sorted copy of the sequence A, denoted as B. O(nlog(n)) time.

[2]Use Longest Common Subsequence on with A and B. O(n2) time.

,I got Wrong Answer .

This is my c++ code

`//Global Variable`

int A[100],B[100];

int DP[100][100];

//This function Finds the Longest common subsequce of Array A[1,2,3...,N] and B[1,2,3...,N]

void LIS(int N)

{

sort((B+1),(B+1)+N);//STL SORT sort from index 1 to N of Array B.

int i,j;

//Base Cases

for(i=0;i<=N;++i)

DP[i][0]=0;

for(j=0;j<=N;++j)

DP[0][j]=0;

for(i=1;i<=N;++i)

{

for(j=1;j<=N;++j)

{

if(A[i]==B[j])

DP[i][j]=DP[i-1][j-1]+1;

else

DP[i][j]=max(DP[i-1][j],DP[i][j-1]);

}

}

printf("%d\n",DP[N][N]);

}

int main()

{

int N,i;

scanf("%d",&N);

for(i=1;i<=N;++i)

{

scanf("%d",&A[i]);

B[i]=A[i];

}

LIS(N);

return 0;

}

I don't know why i am getting the Wrong Answer.Can You please Help me in Finding the Bug. Or the LIS by LCS Algorithm given in the site is incorrect??

Answer

The Second Method is correct, but can't be applied to this problem directly. That's because the numbers in the sequence are not guaranteed to be unique in this SPOJ problem, and the target is to find a **strict increasing** subsequence, while Your Second Method's output is **non-decreasing** subsequence here. Demonstrating on a simple test case `[1,2,2,3]`

will help you find the difference.

This solution is also simple: just remove the duplicated elements after sorting.