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

我一直试图理解这个算法过去两个小时，但似乎无法得到它。有人可以用简单易懂的方式解释吗？解释算法来解决'最长的递增子序列'问题

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;

来源

2011-09-02 missingfaktor

用铅笔和纸张上的十元素数组遍历代码。或者返回到该功能的文档。 –

^@ RaymondChen 这是如此无益。最好不要发布任何内容，而不要提出这样的建议。它降低了本网站的答案质量，它只会损害社区并延伸自己。 – guribe94

在第一个（双）循环终止之后，q[i]是结束于位置i的最长增加子序列的长度。

要看到双回路是如何工作的，假设q[j]已经包含在j位置结束最大的递增子的长度，但只为j0和k-1之间。鉴于此，你将如何计算q[k]？

那么，你会发现所有的j与j < k和a[j] < a[k]的，看看哪些相应q[j]值最大，增加一个，并在q[k]藏匿该值。这正是内循环所做的。

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

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

来源

2011-09-02 14:45:25 Nemo

对于每个元素设定当前元素制成的元件的最长子的计数通过当前元素元件之前最长子之一的长度递增，使得它们的最大值大于当前元素的值小。

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

来源

2011-09-02 14:28:15 Dialecticus

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

回答

相关问题