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:
“There comes a point in many people’s lives when they can no longer play the role they have chosen for themselves. When that happens, we are like actors finding that someone has changed the play.”
—Brian Moore (b. 1921)
“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)
“Without looking, then, to those extraordinary social influences which are now acting in precisely this direction, but only at what is inevitably doing around us, I think we must regard the land as a commanding and increasing power on the citizen, the sanative and Americanizing influence, which promises to disclose new virtues for ages to come.”
—Ralph Waldo Emerson (1803–1882)