149 : 和が最大となる部分列の探索

下の表において, 任意の方向(縦横斜め)に隣り合うものの和の最大値は16 (= 8 + 7 + 1)となることは簡単に確かめられる.

-2	5	3	2
9	-6	5	1
3	2	7	3
-1	8	-4	8

いま, 同じ探索をより大きなものについてもしてみることにする.

まず, 400万個の擬似乱数を"Lagged Fibonacci Generator"によって生成する.

$1 ≤ k ≤ 55$について, $s_k = [100003 - 200003k + 300007k^3] (\mod 1000000) - 500000$ $56 ≤ k ≤ 4000000$について,$s_k = [s_{k-24} + s_{k-55} + 1000000] (\mod 1000000) - 500000$

つまり, s10 = -393027 , s100 = 86613 となる.

s の項は, 最初の2000個を最初の行に(順番に), 次の2000個を2番目の行に, というように, 2000x2000の表に並べ替えられる.

任意の方向(縦横斜め)に隣り合うものの和の最大値を求めよ. (連続して足す領域は３マス以上でもよい, 斜め４マス等も認める)