[Haskell-cafe] Re: Longest increasing subsequence

[ChrisK]

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.

-}