module Algorithm.LIS where

import qualified Data.IntSet as IS
import qualified Data.Vector.Unboxed as U

longestIncreasingSubsequence :: U.Vector Int -> Int
longestIncreasingSubsequence :: Vector Key -> Key
longestIncreasingSubsequence Vector Key
xs = IntSet -> Key
IS.size (IntSet -> Key) -> IntSet -> Key
forall a b. (a -> b) -> a -> b
$ (IntSet -> Key -> IntSet) -> IntSet -> Vector Key -> IntSet
forall b a. Unbox b => (a -> b -> a) -> a -> Vector b -> a
U.foldl' IntSet -> Key -> IntSet
step IntSet
IS.empty Vector Key
xs
  where
    step :: IntSet -> Key -> IntSet
step IntSet
s Key
x = case Key -> IntSet -> Maybe Key
IS.lookupGE Key
x IntSet
s of
      Just Key
y
        | Key
x Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
y -> Key -> IntSet -> IntSet
IS.insert Key
x (IntSet -> IntSet) -> IntSet -> IntSet
forall a b. (a -> b) -> a -> b
$ Key -> IntSet -> IntSet
IS.delete Key
y IntSet
s
        | Bool
otherwise -> IntSet
s
      Maybe Key
Nothing -> Key -> IntSet -> IntSet
IS.insert Key
x IntSet
s