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.

Pages: 1 2

4 Responses to “Longest Increasing Subsequence”

  1. Paul said

    In Python.

    def longest_sub_seq(seq):
        piles = []
        for item in seq:
            last_pile = None
            for pile in piles:
                if item < pile[-1][0]:
                    ptr = len(last_pile) - 1 if last_pile else None
                    pile.append((item, ptr))
                    break
                last_pile = pile
            else:
                ptr = len(last_pile) - 1 if last_pile else None
                piles.append([(item, ptr)])
        pile_nr = len(piles) - 1
        item, ptr = piles[pile_nr][0]
        res = [item]
        while ptr is not None:
            pile_nr -= 1
            item, ptr = piles[pile_nr][ptr]
            res.append(item)
        return res[::-1]
    
  2. Francesco said

    Haskell ahoy

    import Control.Monad
    import Data.List

    test = [3,2,6,4,5,1]

    lsbs cs = filter ((==ml) . length) sortonly
    where sortonly = filter (\\a -> sort a == a) (subs cs)
    ml = maximum $ map length sortonly
    subs cs = filterM (\\a -> [True, False]) cs

    main = print $ lsbs test

  3. Francesco said

    ok, formatting didn’t go easy on me.
    Same snippet on codepad

    http://codepad.org/TgbMu3oq

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: