import qualified Data.Array as Array


burstDP :: [Int] -> Int
burstDP l = go 1 len
  where
    go left right | left <= right = maximum [ds Array.! (left, k-1)
                                            + ds Array.! (k+1, right)
                                            + b (left-1)*b k*b (right+1) | k <- [left..right]]
                  | otherwise    = 0
    len = length l
    ds = Array.listArray bounds
           [go m n | (m, n) <- Array.range bounds]
    bounds = ((0,0), (len+1, len+1))
    l' = Array.listArray (0, len-1) l
    b i = if i == 0 || i == len+1 then 1 else l' Array.! (i-1)