Haskell: brute force and maximum subarray problem

Question

I am trying to solve the maximum sub array problem with a brute force approach i.e generating all the possible subarrays combinations. I got something that works but it's not satisfying at all because it produces way too many duplicated subarrays.

Does anyone knows a smart way to generate all the subarrays (in [[]] form) with a minimal number of duplicated elements ?

By the way, I'm new to Haskell. Here's my current solution:

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

There are many useful functions for operating on lists in the standard Data.List module.

import Data.List

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

Answer 2

dave4420's answer is how to do what you want to do using smart, concise Haskell. I'm no Haskell expert, but I occasionally play around with it and find solving a problem like this to be an interesting distraction, and enjoy figuring out exactly why it works. Hopefully the following explanation will be helpful :)

The key property of dave4420's answer (which your answer doesn't have) is that the pair (startPos, endPos) is unique for each subarray it generates. Now, observe that two subarrays are distinct if either their startPos or endPos is different. Applying inits to the original array returns a list of subarrays that each have unique startPos, and the same endPos (equal to the number of elements in the array). Applying tails to each of these subarrays in turn produces another list of subarrays -- one list of subarrays is output per input subarray. Notice that tails does not disturb the distinctness between input subarrays because the subarrays output by invoking tails on a single input subarray all retain the same startPos: that is, if you have two subarrays with distinct startPoses, and put both of them through tails, each of the subarrays produced from the first input subarray will be distinct from each of the subarrays produced from the second one.

Additionally, each of the subarrays produced by the invocation of tails on a single subarray are distinct because, although they all share the same startPos, they all have distinct endPoses. Therefore all subarrays produced by (concatMap tails) . inits are distinct. It only remains to note that no subarray is missed out: for any subarray starting at position i and ending at position j, that subarray must appear as the j-i+1th list produced by applying tails to the i+1th list produced by inits. So in conclusion, every possible subarray appears exactly once!