haskell - 在整数列表中搜索，按增长排序的最长有序子集(不一定是连续的)之一

Question

函数，在整数列表中查找下标(不一定是连续的)数字的最长有序增量之一。示例:

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

我对从数组中获取初始数字并查找序列的函数有疑问:

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

我有问题，14,18,16,14,17,22,13 14 < 18 但然后 18 > 16 我的算法以数字 16 作为基础，正在寻找新的序列，我需要返回到 14 我该怎么做？

(对不起我的英语)

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 长度。

代码如下:

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] 作为最大子序列，如果您允许的话，这可能没问题。