Problem 150

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 $ 0 
    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 0
                 | otherwise = map (r!).scanl (+) y$[h..]
          right y =  map (r!).scanl (+) y$[h+1..]
          h = length (x:xs)

main = print.foldl' msst 0 .take height.triangle 1$[1..]

十分速いとはいえない。
部分三角形は全部でO(n^3)あるので、O(n^2)のアルゴリズムはないようにも思えるが、
最大部分列和問題はO(n)のアルゴリズムがあるので、
いいアルゴリズムがあるかもしれない。