解释如何解决“最长递增子序列”问题的算法。

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;

- missingfaktor

---

用铅笔和纸遍历十个元素的数组代码。或者回到函数的文档。 - Raymond Chen

这样做没有任何帮助。不发表任何建议比提供这样的建议更好。这会削弱该网站的答案质量，对社区和您自己都没有任何好处。 - guribe94

Answer 1

在第一次（双重）循环终止后，q [i] 是以位置 i 结尾的最长递增子序列的长度。

为了了解双重循环的工作原理，假设q [j] 已经包含在位置 j 结束时最大递增子序列的长度，但仅对于j 在0和k-1之间。在此基础上，您将如何计算q [k]？

嗯，您将找到所有j，其中j且a [j] ，查看相应的q [j]值中哪一个最大，然后加1，并将该值存储在q [k]中。这正是内部循环所做的。

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

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

- Nemo

Answer 2

对于每个元素，将由当前元素构成的最长子序列的计数增加1，该子序列是由前面的元素组成的，其最大值小于当前元素。

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

- Dialecticus