Proof of Longest Increasing Subsequence using greedy patience sort

Question

I came across the solution that uses Patience sort to obtain the length of the Longest Increasing Subsequence (LIS). http://www-stat.stanford.edu/~cgates/PERSI/papers/Longest.pdf, and here - http://en.wikipedia.org/wiki/Patience_sorting.

The proof that following the greedy strategy actually gives us the length correctly has 2 parts -

1. proves that the number of piles is at least equal to the length of the LIS.
2. proves that the number of piles using greedy strategy is at most equal to the LIS.

Thus by virtue of both 1) and 2), the solution gives the length of LIS correctly.

I get the explanation for 1), but I just cannot intuitively realize part 2). Can someone may be use a different example to convince me that this is indeed true. Or, you could even use a different proof technique too.

Answer 1

I just read over the paper and I agree that the proof is a bit, um, terse. (I'd say that it's missing some pretty important steps!)

Intuitively, the idea behind the proof is to show that if you play with the greedy strategy and at the end of the game pick any card in a pile numbered p, you can find an increasing subsequence in the original array whose length is p. If you can prove this fact, then you can conclude that the maximum number of piles produced by the greedy strategy is the length of the longest increasing subsequence.

To formally prove this, we're going to argue that the following two invariants hold at each step:

1. The top cards in each pile, when read from left to right, are in sorted order.

2. At any point in time, every card in every pile is part of an increasing subsequence whose length is given by the pile index.

Part (1) is easy to see from the greedy strategy - every element is placed as far to the left as possible without violating the rule that smaller cards must always be placed on top of larger cards. This means that if a card is put into pile p, we are effectively taking a sorted sequence and reducing the value of the pth element to a value that's greater than whatever is in position p - 1 (if it exists).

To see part (2), we'll go inductively. The first placed card is put into pile 1, and it's also part of an increasing subsequence of length 1 (the card by itself). For the inductive step, assume that this property holds after placing n cards and consider the (n+1)st. Suppose that it ends up in pile p. If p = 1, then the claim still holds because this card forms an increasing subsequence of length 1 all by itself. Otherwise, p > 1. Now, look at the card on top of pile p - 1. We know that this card's value is less than the value of the card we just placed, since otherwise we would have placed the card on top of that pile. We also know that the card on top of that pile precedes the card we just placed in the original ordering, since we're playing the cards in order. By our existing invariant, we know that the card on top of pile p - 1 is part of an increasing subsequence of length p - 1, so that subsequence, with this new card added into it, forms an increasing subsequence of length p, as required.