2

ウィキペディアで指定された最長増加サブシーケンスの擬似コードを次に示します

L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
    such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] < X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)

コードの仕組みは理解できました。私が理解できない唯一のことは、このステートメントの必要性です(if j == L or X[i] < X[M[j+1]]:)私は多くの例でアルゴリズムを実行しようとしましたが、私が理解できることすべてのケースで j == L または X[i] < X[M[j+1]] のいずれかであり、if ステートメントは常に True と評価されます。if ループが false で、アルゴリズムに必要な例を教えてください。

4

1 に答える 1

3

重複がある場合、if条件は失敗します

検討X={2, 2, 2}

ifj=0条件が満たされない場合L=1

于 2013-07-05T07:13:27.177 に答える