Why does Patience sorting find the longest increasing subsequence?
With the two insights from (II) it is obvious that no increasing sequence can use two cards (or more) from one pile.

This means: No increasing sequence can use more cards then the number of piles.
But patience sort returns the number of piles.

So: patienceSort(seq) &gt;= correct(seq)

See also: Slides from Princeton with pictures.

Thank you very much Yuval Filmus :-)