ritesh_NITW - 1 year ago 95
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.
``````

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??

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.