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 >= 0 = map (a!) .genericTake (m-n) $[n+1,n+2+m..m^2]
             | n <  0 = map (a!) [m*(-n)+1,m*(-n+1)+2..m^2]

antiDiag a n | n >= 0 = map (a!) .genericTake (m-n) $[m-n,2*m-n-1..m^2]
             | n <  0 = map (a!) [m*(-n+1),m*(-n+2)-1..m^2]

mss :: [Integer] -> Integer
mss = fst.foldl' f (0,0)
    where  f (max',sum) x = let sum' = max 0 $ 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

あんまり速くない。