import qualified Data.List as List (permutations)

burst :: [Int] -> (Int, [Int])
burst = burstNaive

burstNaive :: [Int] -> (Int, [Int])
burstNaive = foldl (a@(aVal,_) e@(eVal,_) -> if eVal > aVal then e else a) (0, []) . allOrders

allOrders :: [Int] -> [(Int, [Int])]
allOrders []       = []
allOrders l@(x:xs) = map (p -> (flip withOrder l p, p))$ List.permutations [0..length l - 1]

type IndexOrder = [Int]
withOrder :: IndexOrder -> [Int] -> Int
withOrder []     _  = 0
withOrder (i:is) xs = left * (xs !! i) * right + withOrder adjust xss
  where
    xss = remAt i
    adjust = map (index -> if index > i then index - 1 else index) is
    left  = if i == 0 then 1 else xs !! (i-1)
    right = if i == (length xs - 1) then 1 else xs !! (i+1)
    remAt index = let (f,s) = splitAt index xs in f ++ drop 1 s

Prelude> :l Balloon.hs
[1 of 1] Compiling Balloon          ( Balloon.hs, interpreted )
Ok, one module loaded.
*Balloon> burst [3,1,5,8]
(167,[1,2,0,3])
*Balloon>