algorithm - 使用贪婪耐心排序证明最长递增子序列

Question

我遇到了使用耐心排序来获取最长递增子序列 (LIS) 长度的解决方案。 http://www-stat.stanford.edu/~cgates/PERSI/papers/Longest.pdf ，这里 - http://en.wikipedia.org/wiki/Patience_sorting .

遵循贪婪策略实际上给我们正确长度的证明有 2 个部分 -

1. 证明桩的数量至少等于LIS的长度。
2. 证明使用贪心策略的堆数至多等于LIS。

因此，凭借 1) 和 2)，解决方案正确给出了 LIS 的长度。

我得到了 1) 的解释，但我无法直观地理解第 2) 部分。有人可以用不同的例子来说服我这确实是真的吗？或者，您甚至可以使用不同的证明技术。

Answer 1

我刚刚通读了这篇论文，我同意证明有点，嗯，简洁。 (我会说它缺少一些非常重要的步骤!)

直觉上，证明背后的想法是表明，如果您使用贪心策略进行游戏，并且在游戏结束时从编号为 p 的牌堆中挑选任意一张牌，您可以在原始数组中找到一个递增的子序列，其长度为p.如果你能证明这个事实，那么你就可以得出贪心策略产生的最大堆数就是最长递增子序列的长度。

为了正式证明这一点，我们将论证以下两个不变量在每一步都成立:

1. 从左到右阅读时，每堆中最上面的卡片是按排序顺序排列的。

2. 在任何时间点，每堆中的每张牌都是递增子序列的一部分，其长度由堆索引给出。

第 (1) 部分很容易从贪婪策略中看出 - 每个元素都尽可能地放在左边，而不违反较小的卡片必须始终放在较大的卡片之上的规则。这意味着如果将一张牌放入堆 p，我们实际上是在采用排序序列并将第 p 个元素的值减少到大于位置 p - 1(如果存在)中的任何值。

要查看第 (2) 部分，我们将进行归纳。第一张放置的卡片被放入堆 1，它也是长度为 1 的递增子序列的一部分(卡片本身)。对于归纳步​​骤，假设此属性在放置 n 张牌并考虑第 (n+1) 张牌后成立。假设它最终出现在 p 堆中。如果 p = 1，则声明仍然成立，因为这张卡片本身形成了一个长度为 1 的递增子序列。否则，p > 1。现在，看看 p - 1 堆上面的牌。我们知道这张牌的值(value)小于我们刚刚放置的牌的值(value)，否则我们会把牌放在那堆上面桩。我们还知道那堆牌最上面的牌在我们刚刚按原始顺序放置的牌之前，因为我们是按顺序打牌的。根据我们现有的不变量，我们知道堆 p - 1 顶部的卡片是长度为 p - 1 的递增子序列的一部分，因此，将这张新卡片添加到其中的子序列形成长度为 p 的递增子序列，如需要。