algorithm - 查找以特定元素结尾的最长递增子序列如何导致查找 LIS 的解决方案

Question

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

谢谢。

Answer 1

以这个序列为例:

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。

现在您可以展开序列的其余部分，从后面开始:寻找 LIS的 5 (比元素 50 少一个)使得数字小于 50产量 8。进一步回顾 4给你6 (没有平局，因为 30 高于 8 )。接下来是5与 LIS的 3 , 然后是 2与 LIS的 2 .请注意，即使 20 也没有平局。具有相同的LIS .这是因为 20在5之上.最后，我们找到1与 LIS的 1 , 完成序列:

50  8  6  5  2  1

反转这个会产生最长的递增子序列:

1 2 5 6 8 50

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