我正在尝试用蛮力方法解决最大子数组问题,即生成所有可能的子数组组合。我得到了一些有用的东西,但它根本不令人满意,因为它产生了太多重复的子数组。
有谁知道用最少数量的重复元素生成所有子数组(以 [[]] 形式)的聪明方法?
顺便说一句,我是 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)