liss = maximumBy length . filter ascending . concat . map inits . tails
Of course my solution is braindamaged since I skipped this bit of the
definition: [quote]Note that subsequence we are searching for is not
necessarily contiguous[/quote]. Like the article says, without this detail
the
G'day all.
Quoting Matt Amos [EMAIL PROTECTED]:
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
I'm trying to break out of my imperative mind-set by learning Haskell
in small snippets. After a few successes I've hit a bit of a
roadblock with one of the classic dynamic programming problems, the
longest increasing subsequence:
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
The article mentioned in this thread addresses a similar problem:
http://lambda-the-ultimate.org/classic/message8282.html
The main idea is to start by expressing the straightforward, inefficient
solution ,in this case something like:
liss = maximumBy length . filter ascending . concat . map
On Thursday 10 April 2008 01:20:49 pm Matt Amos wrote:
I'm trying to break out of my imperative mind-set by learning Haskell
in small snippets. After a few successes I've hit a bit of a
roadblock with one of the classic dynamic programming problems, the
longest increasing subsequence:
You can translate the following algorithm (written in Maple 11), which
can be made purely functional. [For the cognoscenti: attributes are
implemented in-place in Maple, but that is really just an instance of
the Decorator pattern which can be just as easily implemented with a
functional
