CODEWITHSUNDEEP
c++dynamic-programming
Ritesh Kumar Gupta
Ritesh Kumar Gupta

Reputation: 5191

Wrong Answer on SPOJ

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

Upvotes: 1

Views: 1139

Answers (1)

RoBa
RoBa

Reputation: 428

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.

Upvotes: 2

Related Questions