algorithm - 解释解决 'longest increasing subsequence'问题的算法

Question

过去两个小时我一直试图理解这个算法，但似乎无法理解。有人可以用通俗易懂的方式解释一下吗？

function lis_length(a)
    n := a.length
    q := new Array(n)
    for k from 0 to n:
        max := 0;
        for j from 0 to k, if a[k] > a[j]:
            if q[j] > max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 0 to n:
        if q[i] > max, then set max = q[i].
    return max;

Answer 1

在第一个(双)循环终止后，q[i]是在位置 i 处结束的最长递增子序列的长度.

要查看双循环的工作原理，假设 q[j]已经包含结束于位置 j 的最大递增子序列的长度, 但仅适用于 j在 0 之间和 k-1 .鉴于此，您将如何计算 q[k] ？

好吧，您会找到所有 j与 j < k和 a[j] < a[k] ，看对应的是哪个q[j] values 是最大的，加一，并将该值存储在 q[k] 中.这正是内部循环所做的。

所以在内循环的入口处，q[j] j 在 0 之间已经有正确的值和 k-1 .在退出时，它也有 k 的正确值.所以当双循环退出时，q[i]所有 i 的值都正确在 0 之间和 n .

最后的循环只是选择其中最大的一个，这就是答案。