1

我在SPOJ上尝试了一个问题，我们必须简单地找到给定数组 A的最长递增子序列的长度。

我已经使用动态编程 O(n^2) 算法解决了这个问题，并且该解决方案被接受了。这是被接受的代码：

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;
}

但是当我尝试使用第二种方法（LINK）解决它时，它是::

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.

，我得到了错误的答案。

这是我的 C++ 代码

//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;
}

我不知道为什么我得到错误的答案。你能帮我找到错误吗？或者站点中给出的 LIS by LCS Algorithm不正确？

4

1 回答 1

2

第二种方法是正确的，但不能直接应用于这个问题。那是因为在这个SPOJ问题中不保证序列中的数字是唯一的，目标是找到一个严格的递增子序列，而Your Second Method的输出在这里是非递减子序列。演示一个简单的测试用例[1,2,2,3]将帮助您找到不同之处。

这个解决方案也很简单：只需在排序后删除重复的元素。

于 2012-07-26T13:51:40.633 回答