Problem 149

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

最大部分列和問題を繰り返し解いているだけ。

import Data.List
import Data.Array.IArray
m = 2*10^3
sArray = sa :: Array Integer Integer
where sa = listArray (1,m^2). map s' $ [1..m^2]
s' k | inRange(1,55) k= (100003 - 200003*k + 300007*k^3) `mod` 1000000 - 500000
| inRange(56,4000000) k = (sa!(k-24) + sa!(k-55) + 1000000) `mod` 1000000- 500000
horizontal a n = map (a!) [(n-1)*m+1..n*m]
vertical a n = map (a!) [n,n+m..m*m]
diagonal a n | n >=  = map (a!) .genericTake (m-n) $[n+1,n+2+m..m^2]
| n <   = map (a!) [m*(-n)+1,m*(-n+1)+2..m^2]
antiDiag a n | n >=  = map (a!) .genericTake (m-n) $[m-n,2*m-n-1..m^2]
| n <   = map (a!) [m*(-n+1),m*(-n+2)-1..m^2]
mss :: [Integer] -> Integer
mss = fst.foldl' f (,)
where  f (max',sum) x = let sum' = max  $ sum+ x
in (max max' sum',sum')
p149 = maximum .map (maximum .map mss) $[h,v,d,a]
where h = map (horizontal sArray) [1..m]
v = map (vertical sArray) [1..m]
d = map (diagonal sArray) [-m+1..m-1]
a = map (antiDiag sArray) [-m+1..m-1]
main = print p149

あんまり速くない。