最大の和

Haskell

http://www.ioi-jp.org/joi/2006/2007-ho-prob_and_sol/2007-ho.pdf の問題1。普通にやっても全然面白くないので、 step 関数で無駄な計算を減らすように少し工夫してみた。が、リストの末尾に要素を追加するコストを考えると毎回計算した方が速い気もする。(length nums に比べ size が小さい場合)

maxsum :: [Int] -> Int -> Int
maxsum nums size = step start (a, start, b)
    where (a,b) = splitAt size nums
          start = sum a
step m (a:aa, now, b:bb) =
    let c = now-a+b in
    (if c > m then step c else step m) (aa++[b], c, bb)
step m _ = m