Longest Increasing Subsequence
September 2, 2014
A sequence is a list of integers (or any other ordered type, but we’ll use integers to keep things simple). A subsequence is any, possibly non-consecutive, list drawn from the parent sequence with items in the same order as the parent sequence. An increasing subsequence is a subsequence with all the items in increasing order. A longest increasing subsequence (there may be more than one with the same length) is an increasing subsequence of a parent sequence of the greatest possible length. For instance, the sequence (3 2 6 4 5 1) has longest increasing subsequences (2 4 5) and (3 4 5).
The algorithm to find the longest increasing subsequence is similar to the algorithm for patience sorting of a previous exercise, with a small modification. When dealing the cards, each time a card is placed on a pile, a back-pointer to the top card on the previous pile is placed along with the card. Then, when all the cards are dealt, the number of piles is the length of the longest increasing subsequence, and the longest increasing subsequence can be recovered by taking the top card from the last pile and following the back-pointers to previous piles.
For instance, with sequence (3 2 6 4 5 1) the cards are dealt with 3 and 2 on the first pile, 6 and 4 on the second pile, 5 on the third pile, and 1 on the first pile, so the longest increasing subsequence has length 3. The 5 on the third pile ends the longest increasing subsequence, it points to the 4 which was on the top of the second pile when 5 was added to the third pile, and 4 points to the 2 which was on the top of the first pile when 4 was added to the second pile; even though 1 was later added to the first pile, is wasn’t yet on the pile when 4 was added to the second pile, so it’s not part of the longest increasing subsequence.
Your task is to write a program to find the longest increasing subsequence of a sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 