0

这可能是一个非常经典的问题，即在 O(nlogn) 中找到最长的非递减子序列。只是为了修改，数组A = {2 4 2 3 3 5 1}中最长的非递减子序列的长度是5 {2 2 3 3 5}。

然而，经过无数次努力，我无法理解我的算法实现在哪里失败。我已经阅读并实现了此处和此处描述的算法，仅对“=”符号进行了一点更改，以允许最长递增子序列的 O(nlogn) 实现中的相等元素。我正在尝试这个问题，其中微不足道的 O(n^2) 方法（当解决方案被接受时是正确的）和 O(nlogn) 方法给出了不同的解决方案（我通过断言语句推断出），这证明了某些事情是错误的确定我的 O(nlogn) 实现。

我的 O(nlogn) 实现如下：

/* Array LNDS will be used for finding
longest non-decreasing subsequence in array A of size n */
int LNDS[n],len=1,x; // len will be storing the required length
fill(LNDS,LNDS+n,0);
LNDS[0]=A[0];
for(int i=1; i<n; i++)
{
    x=LNDS[len-1];
    if(A[i]<LNDS[0])
        LNDS[0]=A[i];
    else if(A[i]>=x) // "=" sign to allow equal elements
        LNDS[len++]=A[i];
    else
    {
        l=0;
        r=len-1;
        while(r-l>1) // binary search for finding lower bound for A[i] in LNDS
        {
            m=(l+r)/2;
            if(LNDS[m]>=A[i]) r=m;
            else l=m;
        }
        LNDS[r]=A[i];
    }
}
return len;
4

0 回答 0