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)

我已经了解代码是如何工作的。我唯一不能理解的是这个语句的必要性（如果 j == L 或 X[i] < X[M[j+1]]:) 我已经尝试在许多示例上运行该算法，我可以做出什么是在所有情况下，要么 j == L 要么 X[i] < X[M[j+1]] ，所以 if 语句总是计算为 True。你能给我一个例子，if循环是假的，因此算法需要吗？

4

1 回答 1

3

当有重复时，if条件将失败

考虑X={2, 2, 2}

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

于 2013-07-05T07:13:27.177 回答