data/problems/149.yml
---
:id: 149
:name: Searching for a maximum-sum subsequence
:url: https://projecteuler.net/problem=149
:content: "Looking at the table below, it is easy to verify that the maximum possible
sum of adjacent numbers in any direction (horizontal, vertical, diagonal or anti-diagonal)
is 16 (= 8 + 7 + 1).\n\n| −2 | 5 | 3 | 2 |\n| 9 | −6 | 5 | 1 |\n| 3 | 2 | 7 | 3
|\n| −1 | 8 | −4 | 8 |\n\nNow, let us repeat the search, but on a much larger
scale:\n\nFirst, generate four million pseudo-random numbers using a specific form
of what is known as a \"Lagged Fibonacci Generator\":\n\nFor 1 ≤ _k_ ≤ 55, _s_<sub><i>k</i></sub>
= [100003 − 200003_k_ + 300007_k_<sup>3</sup>] (modulo 1000000) − 500000. \nFor
56 ≤ _k_ ≤ 4000000, _s_<sub><i>k</i></sub> = [_s_<sub><i>k−24</i></sub> + _s_<sub><i>k−55</i></sub>
+ 1000000] (modulo 1000000) − 500000.\n\nThus, _s_<sub>10</sub> = −393027 and _s_<sub>100</sub>
= 86613.\n\nThe terms of _s_ are then arranged in a 2000×2000 table, using the first
2000 numbers to fill the first row (sequentially), the next 2000 numbers to fill
the second row, and so on.\n\nFinally, find the greatest sum of (any number of)
adjacent entries in any direction (horizontal, vertical, diagonal or anti-diagonal).\n\n"