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. Bespamyatnikh and M. Segal 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 structures.
Read more about this topic: Patience Sorting
Famous quotes containing the words finding, longest and/or increasing:
“To people off alone, as we were, there is something stirring about finding evidences of human labour and care in the soil of an empty country. It comes to you as a sort of message, makes you feel differently about the ground you walk over every day.”
—Willa Cather (1873–1947)
“The longest day must have its close—the gloomiest night will wear on to a morning. An eternal, inexorable lapse of moments is ever hurrying the day of the evil to an eternal night, and the night of the just to an eternal day.”
—Harriet Beecher Stowe (1811–1896)
“As the twentieth century ends, commerce and culture are coming closer together. The distinction between life and art has been eroded by fifty years of enhanced communications, ever-improving reproduction technologies and increasing wealth.”
—Stephen Bayley (b. 1951)