Problem 149: Searching for a Maximum-sum Subsequence

Mathematical Development

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}$.

Directional Maximum Search

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

1. Horizontal: Apply Kadane’s to each of the 2000 rows.
2. Vertical: Apply Kadane’s to each of the 2000 columns.
3. Diagonal (top-left to bottom-right): Apply Kadane’s to each of the $2 \times 2000 - 1 = 3999$ diagonals.
4. 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.

Editorial

After the lagged Fibonacci sequence has been generated, the problem becomes a repeated one-dimensional maximum subarray search. Every admissible contiguous subsequence lies on exactly one row, one column, one main diagonal, or one anti-diagonal, so it is enough to extract each line in those four families and run Kadane’s algorithm on it.

The implementation follows that decomposition literally. It fills the $2000\times2000$ table row by row from the generator, then scans rows and columns directly. For the two diagonal directions, it enumerates all offsets, builds the corresponding line, and again applies Kadane’s algorithm. Because Kadane’s algorithm returns the best contiguous sum in linear time for a single sequence, repeating it across all four line families covers every possible direction while keeping the overall runtime quadratic in the grid size.

Pseudocode

Generate the four million sequence values and place them row by row into a 2000 by 2000 table.

Set the best answer to negative infinity.

For each row:
    run Kadane's algorithm and update the best answer.

For each column:
    collect the column entries, run Kadane's algorithm, and update the best answer.

For each top-left to bottom-right diagonal:
    collect its entries, run Kadane's algorithm, and update the best answer.

For each top-right to bottom-left diagonal:
    collect its entries, run Kadane's algorithm, and update the best answer.

Return the largest value seen in any of these scans.

Complexity Analysis

• 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

#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;
}

"""
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()