http://projecteuler.net/index.php?section=problems&id=150

三角形の高さをnとするとO(n^3)のアルゴリズム。

別のO(n^3)のアルゴリズムも実装したが、そちらより20倍ぐらい速い。

こちらのほうが、領域計算量に関して悪いのだが(rが必要)、なぜか速い。 

import Data.List
import Data.Array.IArray
height = 1000
triangle _ [] = []
triangle n xs = let (y,zs) = splitAt n xs in y:triangle (n+1) zs
s = triangle 1.map toS.tail.iterate next $ 
where next t = (615949*t + 797807) `mod` (2^20)
toS t = t - (2^19)
-- 三角形配列を横方向に累積和
r = listArray (1,div (height*(height+1)) 2).concatMap (scanl1 (+))$s :: Array Int Integer
-- maximum sum of sub triangles 
-- (x:xs) : 高さhの頂点列
msst m (x:xs) = foldl' minSubTri m xs
where minSubTri m y = let m' = minimum.scanl1 (+).take (height+1-h)$ zipWith (-) (right y) (left $ y-1)
in min m m'
left y | y < x = repeat 
| otherwise = map (r!).scanl (+) y$[h..]
right y =  map (r!).scanl (+) y$[h+1..]
h = length (x:xs)
main = print.foldl' msst  .take height.triangle 1$[1..]

十分速いとはいえない。

部分三角形は全部でO(n^3)あるので、O(n^2)のアルゴリズムはないようにも思えるが、

最大部分列和問題はO(n)のアルゴリズムがあるので、

いいアルゴリズムがあるかもしれない。