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. -}