Longest increasing subsequence: Difference between revisions
Content added Content deleted
| Line 458: | Line 458: | ||
lis :: Ord a => [a] -> [a] |
lis :: Ord a => [a] -> [a] |
||
lis |
lis xs = runST $ do |
||
let |
let lxs = length xs |
||
pileTops <- newSTArray (min |
pileTops <- newSTArray (min lxs 1, xs) [] |
||
let bsearchPiles x len = aux 1 len where |
let bsearchPiles x len = aux 1 len where |
||
aux lo hi | lo > hi = return lo |
aux lo hi | lo > hi = return lo |
||
| Line 477: | Line 477: | ||
readArray pileTops (i-1) |
readArray pileTops (i-1) |
||
return $ if i == len+1 then len+1 else len |
return $ if i == len+1 then len+1 else len |
||
len <- foldM f 0 |
len <- foldM f 0 xs |
||
return . reverse =<< readArray pileTops len |
return . reverse =<< readArray pileTops len |
||
where newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e) |
where newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e) |
||