Project Euler

Searching for a Maximum-sum Subsequence

Find the greatest sum of any contiguous subsequence in any direction (horizontal, vertical, diagonal, anti-diagonal) in a 2000 x 2000 table generated by a lagged Fibonacci generator.

Source sync Apr 19, 2026

Problem #0149

Level Level 06

Solved By 5,588

Languages C++, Python

Answer 52852124

Length 231 words

modular_arithmeticlinear_algebrasequence

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).

Problem 149: Searching for a Maximum-sum Subsequence

Generator

The table entries $s_k$ for $k = 1, \ldots, 4000000$ are defined by:

For $1 \le k \le 55$ : $s_k = (100003 - 200003k + 300007k^3) \bmod 10^6 - 500000$
For $k > 55$ : $s_k = (s_{k-24} + s_{k-55} + 10^6) \bmod 10^6 - 500000$

The table is filled row by row: entry at row $i$ , column $j$ (1-indexed) is $s_{1000(i-1)+j}$ . Wait — for a 2000x2000 table: $s_{2000(i-1)+j}$ .

Actually: $s_k$ for $k = 1, \ldots, 4000000$ fills the 2000x2000 table. Entry $(i,j)$ = $s_{2000(i-1)+j}$ .

Algorithm: Kadane’s Algorithm

For each of the four directions, apply Kadane’s algorithm to find the maximum contiguous subsequence sum:

Horizontal: Apply Kadane’s to each of the 2000 rows.
Vertical: Apply Kadane’s to each of the 2000 columns.
Diagonal (top-left to bottom-right): Apply Kadane’s to each of the $2 \times 2000 - 1 = 3999$ diagonals.
Anti-diagonal (top-right to bottom-left): Apply Kadane’s to each of the 3999 anti-diagonals.

Kadane’s Algorithm

For a sequence $a_1, a_2, \ldots, a_n$ :

max_ending_here = 0
max_so_far = -infinity
for each a_i:
    max_ending_here = max(a_i, max_ending_here + a_i)
    max_so_far = max(max_so_far, max_ending_here)
return max_so_far

This runs in $O(n)$ time and $O(1)$ space.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

Generating the table: $O(N^2)$ where $N = 2000$ .
Kadane’s over all directions: $O(N^2)$ per direction (each cell is visited once per direction).
Total: $O(N^2) = O(4 \times 10^6)$ .

Answer

\boxed{52852124}

C++ project_euler/problem_149/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int N = 2000;
    const int SZ = N * N;

    // Generate the lagged Fibonacci sequence
    vector<long long> s(SZ + 1);
    for (int k = 1; k <= 55; k++) {
        long long k2 = (long long)k;
        s[k] = ((100003LL - 200003LL * k2 + 300007LL * k2 % 1000000 * k2 % 1000000 * k2) % 1000000 + 1000000) % 1000000 - 500000;
    }
    // Recompute first 55 more carefully to avoid overflow
    for (int k = 1; k <= 55; k++) {
        long long k2 = (long long)k;
        long long val = 100003LL;
        val = (val - 200003LL * k2 % 1000000 + 1000000) % 1000000;
        // 300007 * k^3 mod 10^6
        long long kk = k2 % 1000000;
        long long k3 = kk * kk % 1000000 * kk % 1000000;
        long long term3 = 300007LL * k3 % 1000000;
        val = (val + term3) % 1000000;
        s[k] = val - 500000;
    }

    for (int k = 56; k <= SZ; k++) {
        s[k] = ((s[k - 24] + s[k - 55]) % 1000000 + 1000000) % 1000000 - 500000;
    }

    // Build the 2000x2000 table
    vector<vector<long long>> table(N, vector<long long>(N));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            table[i][j] = s[N * i + j + 1];

    // Kadane's algorithm
    auto kadane = [](const vector<long long>& a) -> long long {
        long long maxHere = 0, maxSoFar = LLONG_MIN;
        for (long long x : a) {
            maxHere = max(x, maxHere + x);
            maxSoFar = max(maxSoFar, maxHere);
        }
        return maxSoFar;
    };

    long long ans = LLONG_MIN;

    // Horizontal
    for (int i = 0; i < N; i++) {
        ans = max(ans, kadane(table[i]));
    }

    // Vertical
    for (int j = 0; j < N; j++) {
        vector<long long> col(N);
        for (int i = 0; i < N; i++) col[i] = table[i][j];
        ans = max(ans, kadane(col));
    }

    // Diagonal (top-left to bottom-right)
    for (int d = -(N - 1); d < N; d++) {
        vector<long long> diag;
        for (int i = max(0, -d); i < N && i + d < N; i++) {
            diag.push_back(table[i][i + d]);
        }
        if (!diag.empty()) ans = max(ans, kadane(diag));
    }

    // Anti-diagonal (top-right to bottom-left)
    for (int d = 0; d < 2 * N - 1; d++) {
        vector<long long> adiag;
        for (int i = max(0, d - N + 1); i < N && d - i >= 0 && d - i < N; i++) {
            adiag.push_back(table[i][d - i]);
        }
        if (!adiag.empty()) ans = max(ans, kadane(adiag));
    }

    cout << ans << endl;
    return 0;
}

Python project_euler/problem_149/solution.py

"""
Problem 149: Searching for a Maximum-sum Subsequence

Find the greatest sum of any contiguous subsequence in any direction
(horizontal, vertical, diagonal, anti-diagonal) in a 2000x2000 table
generated by a lagged Fibonacci generator.
"""

def solve():
    N = 2000
    SZ = N * N

    # Generate the lagged Fibonacci sequence (1-indexed)
    s = [0] * (SZ + 1)
    for k in range(1, 56):
        s[k] = (100003 - 200003 * k + 300007 * k * k * k) % 1000000 - 500000
    for k in range(56, SZ + 1):
        s[k] = (s[k - 24] + s[k - 55] + 1000000) % 1000000 - 500000

    # Build 2000x2000 table (0-indexed)
    table = []
    for i in range(N):
        row = []
        for j in range(N):
            row.append(s[N * i + j + 1])
        table.append(row)

    # Kadane's algorithm
    def kadane(seq):
        max_here = 0
        max_so_far = float('-inf')
        for x in seq:
            max_here = max(x, max_here + x)
            max_so_far = max(max_so_far, max_here)
        return max_so_far

    ans = float('-inf')

    # Horizontal
    for i in range(N):
        ans = max(ans, kadane(table[i]))

    # Vertical
    for j in range(N):
        col = [table[i][j] for i in range(N)]
        ans = max(ans, kadane(col))

    # Diagonal (top-left to bottom-right)
    for d in range(-(N - 1), N):
        diag = []
        for i in range(max(0, -d), N):
            j = i + d
            if j < 0 or j >= N:
                continue
            diag.append(table[i][j])
        if diag:
            ans = max(ans, kadane(diag))

    # Anti-diagonal (top-right to bottom-left)
    for d in range(0, 2 * N - 1):
        adiag = []
        for i in range(max(0, d - N + 1), min(N, d + 1)):
            j = d - i
            if 0 <= j < N:
                adiag.append(table[i][j])
        if adiag:
            ans = max(ans, kadane(adiag))

    print(ans)

if __name__ == "__main__":
    solve()


\(-2\)	\(5\)	\(3\)	\(2\)

\(9\)	\(-6\)	\(5\)	\(1\)

\(3\)	\(2\)	\(7\)	\(3\)

\(-1\)	\(8\)	\(-4\)	\(8\)