[Haskell-cafe] Longest increasing subsequence

[ajb at spamcop.net]

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?

Cheers,
Andrew Bromage