Search in the list of integers, one of the longest ordered subsets (not necessarily consecutive) ordered by growth

Question

Function, which finds in the list of integers one of the longest ordered increments of subscripts (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 the function which takes the initial number from the 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 in place, 14,18,16,14,17,22,13 14 < 18 but then 18 > 16 and my algorithm takes the number 16 as the basis and is looking for a new sequence and I need to go back to 14 How can I do it?

(sorry for my english)

Answer 1

You could always just use subsequences from Data.List to get all the possible subsequences in a list. When you get these subsequences, just take the sorted ones with this function and filter:

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

Then get the maximum length subsequence with maximumBy(or another method), with the ordering being comparinglength.

Here is what the code could look like:

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)

Which seems to work correctly:

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

Note: used map nub to remove duplicate elements from the sub sequences. If this is not used, then this will return [14,14,17,22] as the maximum sub sequence, which may be fine if you allow this.