最长递增子序列的应用

Question

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。

- john mangual

---

一个长度为mn+1的序列将会有一个长度为m+1（不是m）的递增子序列或者一个长度为n+1（不是n）的递减子序列。16=3x5+1，因此应该存在一个长度为5+1=6的递增或递减子序列。 - Kwariz

抱歉，我收到了问题。 - Imposter

Answer 1

一个有趣的LIS现实应用是Patience Diff，这是由BitTorrent的创始人Bram Cohen所开发的一种diffing算法，被用于Bazaar版本控制系统。

常规的diff算法涉及计算两个文档之间的LCS（最长公共子序列）。虽然这种方法很有效，但存在一个问题，即结果通常不太适合人类阅读。

以下是一个简单的示例，说明常规diff可能会失败：

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

 void func2() {
     x += 2
 }

Patience Diff算法的优点在于它能够更精确地计算差异，更符合人类的处理方式。在先前的情况下，Patience Diff能够更好地捕捉到差异。

 void func1() {
     x += 1
 }

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

简而言之，该算法的步骤如下：

1. 找到两个文档中共同存在的独特行。
2. 从第一个文档中获取所有这样的行，并根据它们在第二个文档中出现的顺序进行排序。
3. 计算结果序列的LIS（通过Patience Sort完成），得到最长匹配序列的行、两个文档之间的对应关系。
4. 对已匹配的行之间的每个行范围递归算法。

请查看the code。

- Max Mouratov