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:
“One of the annoying things about believing in free will and individual responsibility is the difficulty of finding somebody to blame your problems on. And when you do find somebody, it’s remarkable how often his picture turns up on your driver’s license.”
—P.J. (Patrick Jake)
“Once I went so far as to slaughter a woodchuck which ravaged my bean-field,—effect his transmigration, as a Tartar would say,—and devour him, partly for experiment’s sake; but though it afforded me a momentary enjoyment, notwithstanding a musky flavor, I saw that the longest use would not make that a good practice, however it might seem to have your woodchucks ready dressed by the village butcher.”
—Henry David Thoreau (1817–1862)
“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)