Problem 149
Searching for a maximum-sum subsequence
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).
| -2 | 5 | 3 | 2 |
| 9 | -6 | 5 | 1 |
| 3 | 2 | 7 | 3 |
| -1 | 8 | -4 | 8 |
Now, let us repeat the search, but on a much larger scale:
First, generate four million pseudo-random numbers using a specific form of what is known as a “Lagged Fibonacci Generator”:
For 1 ≤ k ≤ 55, sk = [100003 ? 200003k + 300007k3] (modulo 1000000) ? 500000.
For 56 ≤ k ≤ 4000000, sk = [sk?24 + sk?55 + 1000000] (modulo 1000000) ? 500000.
Thus, s10 = ?393027 and s100 = 86613.
The 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.
Finally, find the greatest sum of (any number of) adjacent entries in any direction (horizontal, vertical, diagonal or anti-diagonal).
寻找最大和子序列
观察下面的表格，很容易发现，在所有同一横行、竖列或对角线的任意数量相邻数之和中，最大值是16 (= 8 + 7 + 1)。
| -2 | 5 | 3 | 2 |
| 9 | -6 | 5 | 1 |
| 3 | 2 | 7 | 3 |
| -1 | 8 | -4 | 8 |
现在，让我们再来找一次，不过是在一个更大尺寸的表格中：
首先，使用现在被称为“延迟斐波那契生成器”的方法，生成四百万个伪随机数：
对于1 ≤ k ≤ 55，sk = [100003 ? 200003k + 300007k3] (modulo 1000000) ? 500000。
对于56 ≤ k ≤ 4000000, sk = [sk?24 + sk?55 + 1000000] (modulo 1000000) ? 500000.
如此一来，可以得到s10 = ?393027，而s100 = 86613。
这些s的项随后被填入一个2000×2000的表格，前2000个数字按顺序填入第一行，然后2000个数字在第二行，依此类推。
最后，求所有同一横行、竖列或对角线的任意数量相邻数之和的最大值。