# Why does Patience sorting find the longest increasing subsequence?

According to Wikipedia (link), patience sort finds the longest increasing subsequence of a given sequence. Lets say the longest increasing subsequence of seq has length correct(seq)

Patience sort works like this:

Parameters: A sequence of integers called seq
Output: A number between 0 and the length of seq. Lets call it patienceSort(seq)
Algorithm (in Python):

def patienceSort(seq):
piles = []
for el in seq:
for i in range(len(piles)):
# If there is a pile with a strictly greater element on top,
# place current element on that pile
if piles[i][-1] > el:
piles[i].append(el)
break
# if there is no such pile, create a new one
else:
piles.append([el])
return len(piles)


## What I've understood:

(I) We can guarantee that at every time the top of piles (piles[i][-1]) is ordered in increasing order.

(II) For numbers in the same pile: Numbers are ordered...

(II.1) ... by time (first one in the pile came first)

(II.2) ... by value (first one in the pile has highest value)

(III) The numbers on top of the piles are not necessarily an increasing sequence within seq

(IV) The right pile is always the latest one that was created

Example for (III):

      37
20    38
30    39
40    40
50    70
pile1 pile2
seq = [50,40,70,30,40, 39,38,37,20]
[20,37] is not an increasing sequence in seq


For each card (which is not on the first pile), you can store a pointer to the top of the pile before when you add it to the pile. This way, you can get an increasing sequence by following the pointers and inverting the list. So:

patienceSort(seq) <= correct(seq)


## Question

Why is patienceSort(seq) >= correct(seq)

• Google is your friend. For example, cs.princeton.edu/courses/archive/spring13/cos423/lectures/…. Another example with much more: www-stat.stanford.edu/~cgates/PERSI/papers/Longest.pdf. – Yuval Filmus Nov 10 '13 at 21:44
• @YuvalFilmus: Thanks. The key sentence was "Any increasing sequence can use at most one card from each pile". Combined with (II) it is obvious. Do you think I should delete my question or rather write a (community wiki) answer by my own. (I would also accept your comment as an answer). – Martin Thoma Nov 10 '13 at 21:49
• It's best if you could write an answer in your own words and accept it. – Yuval Filmus Nov 10 '13 at 21:50

With the two insights from (II) it is obvious that no increasing sequence can use two cards (or more) from one pile.
So: patienceSort(seq) >= correct(seq)