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:
“Scholars dream of finding small facts pregnant with great progeny.”
—Mason Cooley (b. 1927)
“A bill... is the most extraordinary locomotive engine that the genius of man ever produced. It would keep on running during the longest lifetime, without ever once stopping of its own accord.”
—Charles Dickens (1812–1870)
“Push, labor, shove,—these words of great power in a city like this. Two years must find me with a living and increasing business, or I quit the city and probably the profession.”
—Rutherford Birchard Hayes (1822–1893)