最长递增次的应用

Question

为了提醒您，我在粗体中输入了最长的递增序列

{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。

Answer 1

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

规则的diff算法涉及到计算两个文档之间的最长公共子序列（Longest Common Subsequence,LCS）。虽然这种方法很有效，但也有一个问题，那就是--结果往往不太适合人类。

常规diff可能失败的简单示例：

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

 void func2() {
     x += 2
 }

在前面的情况下耐心的差异点的差异更好：

 void func1() {
     x += 1
 }

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

简单来说，算法就是：

1. 查找两个文档共用的唯一行。
2. 从第一个文档中提取所有这些行，并根据它们在第二个文档中的外观对它们进行排序。
3. 计算结果序列的列表（通过耐心排序），获得最长的匹配行序列，即两个文档的行之间的对应关系。
4. 在已匹配的行之间的每个行范围上递归算法。