Editing Patience sorting (section)

==Relations to other problems==
Patience sorting is closely related to a card game called Floyd's game. This game is very similar to the game sketched earlier:{{r|Burstein}}

# The first card dealt forms a new pile consisting of the single card.
# Each subsequent card is placed on ''some'' existing pile whose top card has a value no less than the new card's value, or to the right of all of the existing piles, thus forming a new pile.
# When there are no more cards remaining to deal, the game ends.

The object of the game is to finish with as few piles as possible. The difference with the patience sorting algorithm is that there is no requirement to place a new card on the ''leftmost'' pile where it is allowed. Patience sorting constitutes a [[greedy algorithm|greedy strategy]] for playing this game.

Aldous and Diaconis suggest defining 9 or fewer piles as a winning outcome for {{math|''n'' {{=}} 52}}, which happens with approximately 5% probability.<ref name="Aldous">{{cite journal |first1=David |last1=Aldous |author-link1=David Aldous |first2=Persi |last2=Diaconis |author-link2=Persi Diaconis |url=http://www-stat.stanford.edu/~cgates/PERSI/year.html#99 |title=Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem |journal= Bulletin of the American Mathematical Society |series=New Series |volume=36 |issue=4 |pages=413–432 |doi=10.1090/s0273-0979-99-00796-x|year=1999 |doi-access=free }}</ref>

===Algorithm for finding a longest increasing subsequence===
First, execute the sorting algorithm as described above. The number of piles is the length of a longest subsequence. Whenever a card is placed on top of a pile, put a [[back-pointer]] to the top card in the previous pile (that, by assumption, has a lower value than the new card has). In the end, follow the back-pointers from the top card in the last pile to recover a decreasing subsequence of the longest length; its reverse is an answer to the longest increasing subsequence algorithm.

S.&nbsp;Bespamyatnikh and M.&nbsp;Segal<ref name=Bespamyatnikh/> give a description of an efficient implementation of the algorithm, incurring no additional [[asymptotic]] cost over the sorting one (as the back-pointers storage, creation and traversal require linear time and space). They further show how to report ''all'' the longest increasing subsequences from the same resulting [[data structure]]s.