algorithm - Haskell:蛮力和最大子数组问题

Question

我正在尝试解决 maximum sub array problem使用蛮力方法，即生成所有可能的子数组组合。我得到了一些有用的东西，但它一点也不令人满意，因为它产生了太多重复的子数组。

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

顺便说一下，我是 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