用贪婪耐心排序证明最长增长子序列

Question

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

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

1. 证明了桩数是，至少等于LIS的长度。
2. 证明了采用贪婪策略的桩数最多为，等于LIS。

因此，借助于1)和2)，解正确地给出了LIS的长度。

我明白对第2部分的解释，但我无法直观地理解第2部分)。有人可以用不同的例子来说服我这是真的吗？或者，你甚至可以用一种不同的证明技术。

Answer 1

我刚看过报纸，我同意这个证据有点，嗯，简洁。(我想说，它错过了一些相当重要的步骤！)

从直觉上看，证明背后的思想是，如果你玩弄贪婪策略，在游戏结束时，在一堆编号为p的牌中挑选任意一张牌，你可以在原来的数组中找到一个长度为p的递增子序列，如果你能证明这一事实，那么你就可以得出贪婪策略产生的最大堆数是最长的递增子序列的长度。

为了正式证明这一点，我们将论证以下两个不变量在每一步中都是有效的：

1. 当从左到右阅读时，每一堆中最上面的卡片都是按顺序排列的。
2. 在任何时间点上，每一堆中的每一张卡片都是一个不断增长的子序列的一部分，其长度由桩指数决定。

第(1)部分很容易从贪婪的策略中看到--每个元素都尽可能地放在左边，而不违反规则，即小卡必须总是放在大卡的上面。这意味着，如果一张卡片被放入p中，我们实际上是在接受一个排序序列，并将pth元素的值降到一个大于p-1位置的值(如果它存在的话)。

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