查找以特定元素结尾的最长递增子序列如何导致找到LIS的解决方案 [英] How does finding a Longest Increasing Subsequence that ends with a particular element leads to the solution of finding LIS

问题描述

我了解到要找到LIS问题的解决方案，我们需要为每个子序列找到一个LIS，从数组的初始元素到以特定元素(最后一个元素)结束的每个元素开始，但是我是我无法理解如何最终找到给定的未排序数组的LIS，但我也理解这会导致最优的子结构属性，然后可以解决，但如上所述，我不知道如何找到LIS(j)以arr [j]结尾将为我们提供帮助.

I have understood that to find the solution of LIS problem, we need to find a LIS for every subsequence starting from initial element of the array to the each element that ends with a particular element(the last element), but I am not able to understand how would that help in finally finding a LIS of a given unsorted array, I also understand that this leads to an optimal substructure property and then can be solved, but as mentioned, I dont see how finding LIS(j) that ends with arr[j] will help us.

谢谢.

推荐答案

以以下顺序为例:

a[]   : 10 20  1  2  5 30  6  8 50  5  7

它将产生以下LIS[i]序列:

a[]   : 10 20  1  2  5 30  6  8 50  5  7
LIS[] :  1  2  1  2  3  4  4  5  6  3  4

鉴于此序列，您可以立即找到结果的长度及其最后一个元素:长度为6，最后一个元素为50.

Given this sequence, you can immediately find the length of the result, and its last element: the length is 6, and the last element is 50.

现在，您可以从背面开始展开序列的其余部分:查找5的LIS(比元素50的LIS小)，使得该数目小于50的结果为8 .进一步回顾4会得到6(没有领带，因为30在8上方).接下来是5，其中LIS为3，然后是2，其LIS为2.请注意，即使20具有相同的LIS，也不会再打领带.这是因为20高于5.最后，我们找到1和1的LIS，完成序列:

Now you can unfold the rest of the sequence, starting from the back: looking for LIS of 5 (one less than that of element 50) such that the number is less than 50 yields 8. Looking back further for 4 gives you 6 (there is no tie, because 30 is above 8). Next comes 5 with LIS of 3, and then a 2 with LIS of 2. Note that there is no tie again, even though 20 has the same LIS. This is because 20 is above 5. Finally, we find 1 with LIS of 1, completing the sequence:

50  8  6  5  2  1

反向将产生最长的递增子序列:

Reversing this produces the longest increasing subsequence:

1 2 5 6 8 50

这是一个常见的技巧:给定一个表，其中包含您要最大化的函数的值(即长度)，您可以通过回溯该函数的步骤来产生产生该函数(即序列本身)的答案.初始元素的算法.

This is a common trick: given a table with the value of the function that you are maximizing (i.e. the length) you can produce the answer that yields this function (i.e. the sequence itself) by back-tracking the steps of the algorithm to the initial element.

这篇关于查找以特定元素结尾的最长递增子序列如何导致找到LIS的解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！