I am writing an algorithm for finding longs path over several turnpoints given a list of coordinates (that describe a path). The dynamic programming algorithm works nicely in O(kn^2), where k is the number of turnpoints and n number of points. To cut the story short: the slowest part is distance computation between 2 coordinates; the algorithm requires this to be 'k'-times recomputed for the same pair of points. Memoization is not an option (too many points). It is possible to 'invert' the algorithm - but somehow the inverted algorithm is very slow in haskell and eats too much memory. 

It seems to me that the problem is following; you are given an array of arrays of fixed size (plus some dynamically computed value - e.g. this would be the result of zipping the value with the list:

```
arr = [ (2, [10,5,12]), (1, [2,8, 20]), (4, [3, 2, 10]) ]

```

I am trying to find a maximum over the elements of the list plus the fixed value:

```
[12, 9, 21]

```

What I am doing - something like:

```
foldl' getbest (replicate 3 0) arr
getbest acc (fixval, item) = map comparator $ zip acc item
comparator orig new
    | new + fixval > orig = new + fixval
    | otherwise = orig

```

The problem is that a new 'acc' gets built with each call to 'getbest' - which is n^2 which is a lot. Allocation is expensive and this is probably the problem. Do you have any idea how to do such thing efficiently? 

To make it clear: this is the actual code of the function:

```
dynamic2FreeFlight :: Int -> [ Coord ] -> [ Coord ]
dynamic2FreeFlight numpoints points = reverse $ (dsCoord bestPoint) : (snd $ (dsScore bestPoint) !! (numpoints - 2))
    where
        bestPoint :: DSPoint
        bestPoint = maximumBy (\x y -> (getFinalPointScore x) `compare` (getFinalPointScore y)) compresult

        getFinalPointScore :: DSPoint -> Double
        getFinalPointScore sc = fst $ (dsScore sc) !! (numpoints - 2)

        compresult :: [ DSPoint ]
        compresult = foldl' onestep [] points 

        onestep :: [ DSPoint ] -> Coord -> [ DSPoint ]
        onestep lst point = (DSPoint point (genmax lst)) : lst
            where
                genmax :: [ DSPoint ] -> [ (Double, [ Coord ]) ]
                genmax lst = map (maximumBy comparator) $ transpose prepared
                comparator a b = (fst a) `compare` (fst b)
                distances :: [ Double ]
                distances = map (distance point . dsCoord) lst
                prepared :: [ [ (Double, [ Coord ]) ] ]
                prepared 
                    | length lst == 0 = [ replicate (numpoints - 1) (0, []) ]
                    | otherwise = map prepare $ zip distances lst
                prepare :: (Double, DSPoint) -> [ (Double, [ Coord ]) ]
                prepare (dist, item) = (dist, [dsCoord item]) : map addme (take (numpoints - 2) (dsScore item))
                    where
                        addme (score, coords) = (score + dist, dsCoord item : coords)

```