# How to prove the optimality of the "patience sort" algorithm?

I was trying to understand how we can solve the Longest Increasing Subsequence (LIS) problem in O(N log N) time. I came across a sorting algorithm called the patience sort algorithm. To learn it I was going through this document:

https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf

I couldn't understand how the optimality was proved - i.e. why this algorithm leads to a minimum number of piles and correspondingly why it leads to the maximum length increasing subsequence.

In the above document from the weak duality principle (see pg. 5) we can understand that the number of piles ≥ length of any increasing subsequence.

Weak duality principle: How can we use the above principle to prove the strong duality principle (see pg. 6)? If we can prove this, we will have proved the optimality.

Strong duality principle: Thanks for the help.

The weak duality principle says that given any play of patience solitaire, the number of piles (at the end) is no less than the length of any Increasing Subsequence (IS) of the initial sequence of cards.

In particular, the min number of piles is no less than the length of the longest IS of the initial sequence of cards. That is, the weak duality implies the following direction of the strong duality:
$$\quad$$ Min number of piles $$\ge$$ max length of an IS.

Claim: We have
$$\quad$$ Min number of piles $$\le$$ max length of an IS.
Proof. Instead of proving using variables that represent general situations, I will use proving by illustration, which should convince a reasonable human.

Look at this picture, which is also embedded in the question. It shows the situation at the end of patience solitaire using greedy algorithm, starting with sequence 6,3,5,10,J,2,9,A,K,7,4,8,Q of spades.

Consider the queen of spades. At the time when it was to be placed on the last pile, it must appear later than all cards in the previous piles in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards in the piles before the last pile. In particular, it must be larger than the uncovered card in the second last pile, which was the 8 of spades. So, we have
$$\quad$$ $$8,$$ Q
as an IS of the initial sequence.

Consider the 8 of spades. At the time when it was to be placed on second to last pile, it must appear later than all existing cards in the piles to its left in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards to its left. In particular, it must be larger than the uncovered card immediately to its left, which was the 7 of spades. So, we have
$$\quad$$ $$7, 8$$
as an IS of the initial sequence.

Consider the 7 of spades. At the time when it was to be placed on third to last pile, it must appear later than all existing cards in the piles to its left in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards to its left. In particular, it must be larger than the uncovered card immediately to its left, which was the 5 of spades. So, we have
$$\quad$$ $$5, 7$$
as an IS of the initial sequence.

And so on.

In the end, combining all ISs obtained, we will have,
$$\quad$$ $$3,5, 7, 8,$$ Q,
as an IS of the initial sequence.

We can see that every pile contributes exactly one item to the IS. Hence, the number of piles is the same as the length of that IS. So, the number of piles (at the end of greedy algorithm) is at most the length of the longest IS of the initial sequence.

So, the min number of piles for all playing strategies, including the greedy algorithm, is at most the length of the longest IS of the initial sequence. $$\quad \checkmark$$.

The proof above is basically an expansion of the instruction, "follow pointers to obtain IS whose length equals the number of piles" in the lecture note from Princeton quoted in the question. By the way, we can also use the subsequence $$3,5,10,$$ J, A or one of many other subsequences to the same effect.

Combining both "$$\ge$$" and "$$\le$$", we should obtain the equality in the strong duality. Moreover, the proof above shows the greedy algorithm finds both numbers (or, that one number).

Exercise (easy): Let $$P_1, P_2, \cdots, P_k$$ denote the piles we have obtained at the end of the greedy algorithm in its natural order. Show that card $$c$$ is in $$P_i$$ iff the longest IS of the initial sequence that ends at $$c$$ is of length $$i$$.