最长增长子序列的应用

Question

在解决其他CS问题时,LIS(最长的后续子序列)问题有用吗？有一些算法,使用耐心排序,动态编程或决策树.这些在现实生活中如何使用 - 可能是数据流还是其他东西？

提醒你,我加入了最长的序列

{ 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15 }.

作为奖励,有没有办法使用这样的结果:长度为mn + 1的序列将具有长度为m的递增子序列或长度为n的递减子序列？例如我们的列表长度为16,因此应该有一个增加的长度序列5或减少长度为5的序列.在我们的例子中为0,2,6,9,11,15.

同样是长度为8的递增序列或长度为3的递减序列:在我们的例子中为12,10,1.

Answer 1

LIS的一个有趣的实际应用是Patience Diff，这是Bram Cohen（BitTorrent的创建者）开发的一种扩散算法，用于Bazaar版本控制系统中。

常规diff算法涉及计算两个文档之间的LCS（最长公共子序列）。这种方法虽然高效，但存在一个问题，即结果往往不是很友好。

常规差异可能会失败的一个简单示例：

 void func1() {
     x += 1
+}
+
+void functhreehalves() {
+    x += 1.5
 }

 void func2() {
     x += 2
 }

耐心差异算法的优点在于，它可以更精确地计算差异，并且方式与人类的表现更为接近。

在前面的案例中，Patience Diff可以更好地发现差异：

 void func1() {
     x += 1
 }

+void functhreehalves() {
+    x += 1.5
+}
+
 void func2() {
     x += 2
 }

简而言之，该算法是：

看一下代码。