Haskell:蛮力和最大的子阵列问题

Question

我试图用蛮力方法解决最大子阵列问题,即生成所有可能的子阵列组合.我得到了一些有效的东西,但它根本不令人满意,因为它产生了太多重复的子阵列.

有没有人知道用最少数量的重复元素生成所有子数组([[]]形式)的聪明方法？

顺便说一句,我是Haskell的新手.这是我目前的解决方案:

import qualified Data.List as L

maximumSubList::[Integer]->[Integer]
maximumSubList x = head $ L.sortBy (\a b -> compare (sum b) (sum a)) $ L.nub $ slice x
     where 
        -- slice will return all the "sub lists"
        slice [] = []
        slice x = (slice $ tail x) ++ (sliceLeft x) ++ (sliceRight x)

        -- Create sub lists by removing "left" part
        -- ex [1,2,3] -> [[1,2,3],[2,3],[3]]
        sliceRight [] = []
        sliceRight x = x : (sliceRight $ tail x)

        -- Create sub lists by removing "right" part
        -- ex [1,2,3] -> [[1,2,3],[1,2],[1]]
        sliceLeft [] = []
        sliceLeft x = x : (sliceLeft $ init x)

Answer 1

在标准Data.List模块中对列表进行操作有许多有用的函数.

import Data.List

slice :: [a] -> [[a]]
slice = filter (not . null) . concatMap tails . inits