解释求解“最长递增子序列”的算法问题
过去两个小时我一直试图理解这个算法，但似乎无法理解。有人可以用简单易懂的方式解释一下吗？
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;
I have been trying to understand this algorithm for past two hours, but can't seem to get it. Can someone please explain it in easy to understand manner?
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;
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
第一个（双）循环终止后，
q[i]是在位置i处结束的最长递增子序列的长度。要了解双循环的工作原理，假设
q[j]已包含以j位置结束的最大递增子序列的长度，但仅限于j在0和k-1之间。鉴于此，您将如何计算q[k]？好吧，您会找到所有
j且jk 和 a[j]a[k]，查看相应的q[j]值中哪个最大，加一，然后将该值存储在q[k]中。这正是内循环的作用。因此，在进入内部循环时，
q[j]已经具有0和k-1之间的正确 j 值。并且在退出时，它还具有正确的k值。因此，当双循环退出时，q[i]具有0和n之间所有i的正确值代码>.最后的循环只选择其中最大的一个，这就是答案。
After the first (double) loop terminates,
q[i]is the length of the longest increasing subsequence ending at positioni.To see how the double loop works, suppose
q[j]already contained the length of the largest increasing subsequence ending at positionj, but only forjbetween0andk-1. Given this, how would you computeq[k]?Well, you would find all of the
jwithj < kanda[j] < a[k], see which of the correspondingq[j]values was biggest, add one, and stash that value inq[k]. This is exactly what the inner loop does.So at entry to the inner loop,
q[j]already has the correct values for j between0andk-1. And at exit, it also has the correct value fork. So by the time the double loop exits,q[i]has the correct value for allibetween0andn.The final loop just selects the largest of those, which is the answer.
对于每个元素，设置由当前元素构成的元素的最长子序列的计数，增加当前元素之前的元素的最长子序列的一个长度，使得它们的最大值小于当前元素的值。
该算法采用正数数组（元素不能为零或更少）。
For each element set the count of longest subsequence of elements made with current element as incremented by one length of longest subsequence of elements preceding current element such that their largest value is smaller than the value of current element.
The algorithm takes array of positive numbers (can't have zero or less as element).