解释算法来解决"增长最长的子序列"问题

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]？

好吧,你会找到所有的jwith,j < k并a[j] < a[k]查看哪个相应的q[j]值最大,添加一个,并将该值存入q[k].这正是内循环的作用.

因此,在进入内环,q[j]已经具备了与j中的正确的价值观0和k-1.在退出时,它也具有正确的值k.因此,当双循环退出时,q[i]所有和i之间的所有值都是正确的.0n

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