algorithm - 最长递增序列

Question

这是在 Wikipedia 上给出的最长递增子序列的伪代码

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)

我已了解代码的工作原理。我唯一不能理解的是这个声明的必要性(如果 j == L 或 X[i] < X[M[j+1]]:)我已经尝试在许多示例上运行该算法，我可以看出在所有情况下 j == L 或 X[i] < X[M[j+1]] 因此 if 语句的计算结果始终为 True .您能否举一个 if 循环为假且因此是算法所必需的示例？？

Answer 1

当存在重复时，if 条件将失败

考虑 X={2, 2, 2}

if 当 j=0 和 L=1 时条件失败