It is late, but I was not sleepy enough, so here is my first translation of the
algorithm to a functional approach...
{- Quote wikipedia: http://en.wikipedia.org/wiki/Longest_increasing_subsequence
L = 0
M[0] = 0
for i = 1, 2, ... n:
binary search for the largest j ≤ L such that X[M[j]] < X[i] (or set j = 0
if no such value exists)
P[i] = M[j]
if j == L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L, j+1)
-}
{-
X[i] defined for i = 1,2,3…
So X[0] is not defined.
Now, rethink '0' as Nothing, and 1≤j≤L since X[M[0]] is also undefined.
Not that after the binary search that one the three conditions holds:
X[i] ≤ X[M[1]]
"The same or a new minimum value"
P[i] is created and set to Nothing
If X[i] < X[M[1]] then M[1] is changed to i
X[M[j]] < X[i] ≤ X[M[j+1]] for some j<L
"A value greater than the minimum and equal or less than the maximum"
P[i] is set to Just M[j]
If X[i] == X[M[j+1]] then there is no need to update M[j+1]
If X[i] < X[M[j+1]] then M[j+1] is changed to i
X[M[L]] < X[i]
"A new maximum value"
P[i] is set to Just M[L]
M[L+1] is created and set to i
L is set to L+1
Wikipedia is too loose. X[M[1]], X[M[2]], …, X[M[L]] is not "nondecreasing",
but must be strictly increasing. This is really sloppy of wikipedia.
The P[i] are just a stack, create a linked list going in and pull
apart on way out, will by O(N).
If you do not separately track the min and max values, then the
algorithm works like this:
Make a map mu from the set of X[M[j]] to M[j], starting empty.
Make a P as a list of Maybe Int, starting as [].
Note that "size mu" will always by L, and starts off as 0.
For i=1,2,3…:
do a Data.Map.splitLookup using pivot X[i] to get (map1,m,map2) and find which
of the three cases we are in:
If there is a null map2 then third case:
If empty mu then prepend Nothing to P.
else get "M[L]" from "snd (snd (findMax mu))", prepend Just "M[L]" to P.
Create new my by inserting key X[i] with value i to mu.
If there is a null map1 then first case (Note that mu cannot be empty):
Prepend Nothing to P
get min from "fst (findMin mu)"
If X[i] < min then make new mu from replacing key X[i] with value i
with (Data.Map.updateMin).
Otherwise this is the middle case and map1 and map2 are both non-empty.
Get "M[j]" from (snd (findMax map1)) and prepend Just "M[j]" to P.
If 'm' is (Just {}) then "X[i] < X[M[j+1]]" and do not change mu
else change mu to Data.Map.adjust key X[i] with value i on mu
Also: keep track of the length of P, which is ultimate N, where 1≤i≤N.
Each operation in the loop with index i is order "log (i-1)"
Note that the "j" is never explicitly tracked. It is implicit in the order of
the keys of the map "mu".
Once you are done, you have a maximum subsequence length of (size mu),
and the stack P is just the P[i]'s in reverse order. You can get the
last index i of the longest subsequence from (snd (findMax mu)) and
backtrack to get the other i's by carefully popping the stack P (in a
single traversal) and keeping only the indices you need until you
reach a Nothing.
-}
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
