5

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

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;
4

2 回答 2

5

在第一个（双）循环终止后，q[i]是在 position 处结束的最长递增子序列的长度i。

要查看双循环是如何工作的，假设q[j]已经包含在 position 结束的最大递增子序列的长度j，但仅适用于jbetween0和k-1。鉴于此，您将如何计算q[k]？

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

因此，在进入内部循环时，在和q[j]之间已经有了正确的 j 值。并且在退出时，它也具有正确的值。因此，当双循环退出时，和之间的所有值都具有正确的值。0k-1kq[i]i0n

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

于 2011-09-02T14:45:25.943 回答
2

对于每个元素，将由当前元素组成的元素的最长子序列的计数设置为以当前元素之前的元素的最长子序列的一个长度递增，使得它们的最大值小于当前元素的值。

该算法采用正数数组（元素不能为零或更少）。

于 2011-09-02T14:28:15.600 回答