Re: [Haskell-cafe] Longest increasing subsequence

G'day all. Quoting Matt Amos :

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