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 \le k \le 55$, $s_k = [100003 – 200003 k + 300007 k^3] \pmod{1000000} – 500000$.
For $56 \le k \le 4000000$, $s_k = [s_{k-24} + s_{k – 55} + 1000000] \pmod{1000000} – 500000$.
Thus, $s_{10} = -393027$ and $s_{100} = 86613$.
The terms of $s$ are then arranged in a $2000 \times 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).

Given the scale and the method of generation of this data, it is clear that attempting to process it manually would be incredibly time-consuming and prone to error. Therefore, an algorithmic or computational approach would be most appropriate for this task. Let’s get down to creating a pseudo code, which can be later implemented in any programming language of your choice:

1. Generate the random numbers and fill the 2000×2000 table with them as stated in the problem.

2. Initialize a variable, `maxSum`, to hold the max sum of numbers, and set it to 0 at the beginning.

3. For each cell in the table, compute the maximum sum of numbers in all four directions (horizontal, vertical, diagonal, and anti-diagonal), and if any of these sums are greater than the current `maxSum`, update `maxSum`.

4. The steps for finding the maximum sum of numbers in each direction for each cell can be elaborated as:

a. Horizontal: Initialize a variable, `horizSum`, to the value of the current cell. Then, for each subsequent cell in the same row, add its value to `horizSum` if it’s positive. If `horizSum` becomes greater than `maxSum`, update `maxSum`.

b. Vertical: Similarly, initialize a variable, `vertSum`, to the value of the current cell. Then, for each subsequent cell in the same column, add its value to `vertSum` if it’s positive. If `vertSum` becomes greater than `maxSum`, update `maxSum`.

c. Diagonal: Initialize a variable, `diagSum`, to the value of the current cell. Then, for each subsequent cell diagonally downwards from the current cell, add its value to `diagSum` if it’s positive. If `diagSum` becomes greater than `maxSum`, update `maxSum`.

d. Anti-diagonal: The process is similar to diagonal, but in this case, move diagonally upwards.

5. After processing all cells in this manner, `maxSum` will hold the largest possible sum of adjacent numbers in any direction.

Such an approach would need a tool like Python, Java, or C++ to be implemented and then could efficiently solve the problem.

More Answers: