algorithm - O(nlogn) 内の最長の非減少サブシーケンス

Question

これは、O(nlogn) で最長の非減少サブシーケンスを見つけるという非常に古典的な問題である可能性があります。修正するために、配列 A={2 4 2 3 3 5 1} の最長の非減少サブシーケンスの長さは 5 {2 2 3 3 5} です。

ただし、数え切れないほどの努力の結果、アルゴリズムの実装がどこで失敗しているのかを理解できません。こことここで説明されているアルゴリズムを読んで実装しましたが、「=」記号を少し変更して、最長増加サブシーケンスの O(nlogn) 実装で等しい要素を許可します。単純な O(n^2) アプローチ (解決策が受け入れられたので正しい) と O(nlogn) アプローチが異なる解決策 (assert ステートメントで推測した) を提供しているこの問題を試みています。私の 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;