[Haskell-cafe] Longest increasing subsequence

ajb at spamcop.net ajb at spamcop.net
Thu Apr 10 20:11:50 EDT 2008

G'day all.

Quoting Matt Amos <matt at asklater.com>:

> http://en.wikipedia.org/wiki/Longest_increasing_subsequence
> The most efficient algorithm relies on destructive updates, so a
> simple translation doesn't seem possible.

Given that it's based on binary search, you might like to try using a
binary search tree.

You may or may not have discovered that the quadratic algorithm has a
more-or-less direct translation into Haskell using lazy arrays.  Did you
have a go at implementing that first?

Andrew Bromage

More information about the Haskell-Cafe mailing list