Searching a list of integers, one of the longest ordered subsets (not necessarily sequential), ordered by height

Question

A function that finds in the list of integers one of the longest ordered increments of indices (not necessarily consecutive) numbers. Example:

• Sequence [21,27,15,14,18,16,14,17,22,13]=[14,16,17,22]

I have a problem with a function that takes a seed from an array and looks for a sequence:

fstLen:: Int -> [Int] -> [Int]    
fstLen a [] = a: []    
fstLen x (l:ls) = if x < l then x:(fstLen l ls) else fstLen x ls

I have problems 14,18,16,14,17,22,13 14 <18, but then 18> 16, and my algorithm takes the number 16 as the base and looks for a new sequence, and I need to go back to 14 How can I do it?

(sorry for my English)

Answer 1

subsequences Data.List, . , filter:

isSorted :: (Ord a) => [a] -> Bool
isSorted [] = True
isSorted [_] = True
isSorted(x:y:xs) = x <= y && isSorted (y:xs)

maximumBy ( ), comparing length.

:

import Data.Ord (comparing)
import Data.List (subsequences, maximumBy, nub)

isSorted :: (Ord a) => [a] -> Bool
isSorted [] = True
isSorted [_] = True
isSorted(x:y:xs) = x <= y && isSorted (y:xs)

max_sequence :: (Ord a) => [a] -> [a]
max_sequence xs = maximumBy (comparing length) $ map nub $ filter isSorted (subsequences xs)

, :

*Main> max_sequence [21,27,15,14,18,16,14,17,22,13]
[14,16,17,22]

: map nub . , [14,14,17,22] , , .

Answer 2

n log n ,

• .
• : ( , )

, .

traceShow , , :

import Debug.Trace (traceShow)
import Data.Map (empty, elems, insert, delete, lookupGT, lookupLT)

-- longest (strictly) increasing sequence
lis :: (Ord k, Show k, Foldable t) => t k -> [k]
lis = snd . maximum . elems . foldr go empty
  where
  go x m = traceShow m $ case x `lookupLT` m of
    Nothing -> m'
    Just (k, v) -> if fst a < fst v then m' else k `delete` m'
    where
    a = case x `lookupGT` m of
      Nothing -> (1, [x])
      Just (_, (i, r)) -> (i + 1, x:r)
    m' = insert x a m

\> lis [21,27,15,14,18,16,14,17,22,13]
fromList []
fromList [(13,(1,[13]))]
fromList [(22,(1,[22]))]
fromList [(17,(2,[17,22])),(22,(1,[22]))]
fromList [(14,(3,[14,17,22])),(17,(2,[17,22])),(22,(1,[22]))]
fromList [(16,(3,[16,17,22])),(17,(2,[17,22])),(22,(1,[22]))]
fromList [(16,(3,[16,17,22])),(18,(2,[18,22])),(22,(1,[22]))]
fromList [(14,(4,[14,16,17,22])),(16,(3,[16,17,22])),(18,(2,[18,22])),(22,(1,[22]))]
fromList [(15,(4,[15,16,17,22])),(16,(3,[16,17,22])),(18,(2,[18,22])),(22,(1,[22]))]
fromList [(15,(4,[15,16,17,22])),(16,(3,[16,17,22])),(18,(2,[18,22])),(27,(1,[27]))]
[15,16,17,22]

. (.. ).

Answer 3

! .

Still improving my answer. The answer below adds up to build the growing subsequences on the right. It also uses the list monad to add new elements to subsequences if the new element is smaller than the head of the subsequence. (This is my first real list monad application.) For example,

λ> [[3], [1]] >>= (prepIfSmaller 2)
[[2,3],[3],[1]]

This solution is about as short as I can do it.

import Data.List (maximumBy)

maxSubsequence :: Ord a => [a] -> [a]
maxSubsequence [] = []
maxSubsequence xs = takeLongest $ go [] xs
  where
    takeLongest :: Ord a => [[a]] -> [a]
    takeLongest = maximumBy (\ x y -> compare (length x) (length y))
    go :: Ord a => [[a]] -> [a] -> [[a]]
    go = foldr (\x subs -> [x] : (subs >>= (prepIfSmaller x)))
      where prepIfSmaller x s@(h:_) = (if x < h then [x:s] else []) ++ [s]

Quick test.

λ> maxSubsequence [21,27,15,14,18,16,14,17,22,13]
[15,16,17,22]