Problem 149: Searching for a Maximum-Sum Subsequence

Project Euler Problem 149 Solution

EulerSolve provides an optimized solution for Project Euler Problem 149, Searching for a Maximum-Sum Subsequence, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary A $2000 \times 2000$ table is filled row by row with a pseudo-random sequence $s_1,s_2,\dots,s_{4{,}000{,}000}$. Among every row, every column, and both diagonal families, we must find the contiguous segment whose sum is as large as possible. The difficulty is not generating the table; it is that the search space of all contiguous segments is enormous if approached naively. The crucial simplification is that each admissible segment lies on a single one-dimensional line, and each such line can be solved optimally by the standard maximum-subarray recurrence. Mathematical Approach Let $n=2000$. The implementations first generate the centered lagged sequence, reinterpret it as an $n \times n$ matrix, and then reduce the entire problem to repeated one-dimensional scans. The Lagged Sequence and the Grid For $1 \le k \le 55$, the values are defined by $$s_k=\left(100003-200003k+300007k^3 \bmod 10^6\right)-500000.$$ For $56 \le k \le n^2$, the recurrence becomes $$s_k=\left(s_{k-24}+s_{k-55}+10^6 \bmod 10^6\right)-500000.$$ After the reduction modulo $10^6$, every entry lies in the interval $[-500000,499999]$....

Detailed mathematical approach

Problem Summary

A table is filled with pseudo-random numbers from a lagged Fibonacci generator. For $1\le k\le55$ the terms are

$$\begin{aligned}s_k&=\bigl(c_k\bmod 10^6\bigr)-500000,\\c_k&=100003-200003k+300007k^3,\end{aligned}$$

and for $56\le k\le4\,000\,000$ they are

$$\begin{aligned}s_k={}&\bigl(s_{k-24}+s_{k-55}+10^6\bigr)\\&\bmod 10^6-500000,\end{aligned}$$

where $x\bmod 10^6$ is the remainder of $x$ on division by $10^6$. The statement gives $s_{10}=-393027$ and $s_{100}=86613$. The four million terms fill a $2000\times2000$ table row by row: $s_1,\dots,s_{2000}$ form the first row, $s_{2001},\dots,s_{4000}$ the second, and so on. We must find the greatest sum of any number of adjacent entries in one direction: horizontal, vertical, diagonal or anti-diagonal. In the $4\times4$ example of the statement,

$$\begin{pmatrix}-2&5&3&2\\9&-6&5&1\\3&2&7&3\\-1&8&-4&8\end{pmatrix},$$

the greatest such sum is $16=8+7+1$, taken along an anti-diagonal. ^[1]

The whole solution in one sentence: every group of adjacent entries lies along a single row, column, diagonal or anti-diagonal, so we walk once along each of these lines, decide at each entry whether to extend the current group or to start a new one, and keep the largest sum seen.

Mathematical Approach

We first study the generator, then turn the search in the table into searches along single lines, and solve each of those in one pass.

1. The first terms

For $k=1$ the cubic $c_k$ of the first rule is $100003-200003+300007$${}=200007$, already below $10^6$, so $s_1=200007-500000$${}=-299993$. For $k=10$ it is $298106973$; the remainder on division by $10^6$ is $106973$, and $s_{10}=106973-500000$${}=-393027$, the first value given in the statement. Since $k^3\ge k$, we have $c_k\ge100004k+100003\ge200007$ for every $k\ge1$, so the cubic is always positive and its remainder is the usual one in every programming language. It does outgrow 32-bit integers: $c_{55}=49902764463$.

2. The lagged rule

From $k=56$ on, each term is made from the terms $24$ and $55$ places earlier. Shifting all terms by $500000$ shows what the rule really does: with $t_k=s_k+500000$, the number $s_{k-24}+s_{k-55}+10^6$ equals $t_{k-24}+t_{k-55}$, so for every $k\ge56$

$$t_k=\bigl(t_{k-24}+t_{k-55}\bigr)\bmod 10^6.$$

This is an additive lagged Fibonacci generator with the lags $24$ and $55$, a popular pair: ^[3] like a Fibonacci number, each new term is the sum of two earlier ones, here reduced modulo $10^6$. Hence $0\le t_k\le999999$, and every term $s_k$ lies between $-500000$ and $499999$; both ends occur among the four million terms.

The $+10^6$ keeps the number to be divided between $0$ and $1999998$. Without it, C++ and Java, whose integer division rounds towards zero, could return a negative remainder for a negative sum, while Python's remainder on division by a positive number is never negative. ^[6] The second value of the statement can be checked by hand: $s_{76}=-151130$ and $s_{45}=-262257$ give $-151130-262257+10^6$${}=586613$, already below $10^6$, so $s_{100}=586613-500000=86613$.

3. The table

Let $n=2000$ and number the rows and columns from $1$ to $n$. The rows above row $i$ use $(i-1)n$ terms, so the entry in row $i$ and column $j$ is

$$a_{i,j}=s_{(i-1)n+j}.$$

For example, row $2$ starts with $a_{2,1}=s_{2001}=-380283$. Programs count from $0$: with $r=i-1$ and $c=j-1$ the entry is term number $rn+c+1$. Storing a table row after row in this way is called row-major order. ^[4]

4. Groups of adjacent entries lie on lines

Adjacent entries in one direction form a straight run of $L$ cells $(i+mu,\,j+mv)$, $m=0,1,\dots,L-1$, with the step $(u,v)$ equal to $(0,1)$ horizontally, $(1,0)$ vertically, $(1,1)$ diagonally and $(1,-1)$ anti-diagonally. A run read backwards has the same sum, so these four steps cover all eight compass directions; the run $8+7+1$ of the example, read downwards, is the run $1,7,8$ with step $(1,-1)$. The cells of a run share their row, their column, their difference $j-i$ or their sum $i+j$, according to its direction. Hence every run is an unbroken piece, a segment, of exactly one line of its direction:

$n$ rows and $n$ columns, each with $n$ cells;
$2n-1$ diagonals, one for each $d=j-i$ from $-(n-1)$ to $n-1$, with $n-|d|$ cells;
$2n-1$ anti-diagonals, one for each $q=i+j$ from $2$ to $2n$, with $n-|q-n-1|$ cells.

The diagonals have $1,2,\dots,n-1,n,n-1,\dots,2,1$ cells, $n^2$ in total, and so do the anti-diagonals. The table has $6n-2=11998$ lines, the example $22$, and the answer is the largest of their best segment sums. The table contains positive entries, such as $s_3=100183$, so the answer is positive, and it makes no difference whether an empty group with sum $0$ would count.

5. Too many segments to try one by one

A line with $L$ cells has $L(L+1)/2$ segments, one for each choice of a first and a last cell. The rows and columns together have $2n\cdot n(n+1)/2=n^2(n+1)$ segments. Each diagonal family has two lines with $\ell$ cells for every $\ell=1,\dots,n-1$ and one with $n$ cells. The sum of the first $m$ triangular numbers $\ell(\ell+1)/2$ is the tetrahedral number $m(m+1)(m+2)/6$, ^[5] so each diagonal family has $(n-1)n(n+1)/3+n(n+1)/2$ segments. Altogether there are

$$\begin{aligned}&n^2(n+1)+\frac{2(n-1)n(n+1)}{3}\\&\quad+n(n+1)=\frac{n(n+1)(5n+1)}{3}\end{aligned}$$

segments, a single cell being counted once on each of its four lines: $140$ for the example and $13\,341\,334\,000$ for $n=2000$. Prefix sums make each of them cheap: with $P_0=0$ and $P_t=x_1+\dots+x_t$ along a line, the segment from position $a+1$ to position $b$ has the sum $P_b-P_a$. ^[2] Still, more than $1.3\cdot10^{10}$ subtractions are wasteful. The method of the next section makes one step per cell and family, $4n^2=16\,000\,000$ steps, more than $800$ times fewer.

6. The best segment that ends at a given cell

Take one line with the entries $x_1,\dots,x_L$ in order, and let $B_t$ be the largest sum of a segment that ends at position $t$. Such a segment is either the single entry $x_t$, or a segment that ends at position $t-1$ followed by $x_t$. The largest sum of the second kind is $B_{t-1}+x_t$, because adding the same $x_t$ to every candidate does not change which candidate is largest. Hence

$$\begin{aligned}B_1&=x_1,\\B_t&=\max\bigl(x_t,\;B_{t-1}+x_t\bigr)\quad(t\ge2).\end{aligned}$$

Every segment ends somewhere, so the best segment sum of the line is the largest of $B_1,\dots,B_L$. This is Kadane's algorithm, ^[2] a small example of dynamic programming: the best answer for position $t$ is built from the one for position $t-1$, and nothing else about the past is needed. In the form $B_t=x_t+\max(B_{t-1},0)$ the rule says: keep the run so far when its best sum is positive, and otherwise start afresh at $x_t$, because putting a run with a negative sum in front of $x_t$ can only lower the sum.

In terms of the prefix sums of Section 5, the best segment ending at $t$ starts right after the lowest earlier prefix sum,

$$B_t=P_t-\min\bigl(P_0,P_1,\dots,P_{t-1}\bigr),$$

and for $t\ge2$ a fresh start is strictly better than extending exactly when $B_{t-1}\lt0$, that is, when $P_{t-1}$ is lower than every prefix sum before it; if $B_{t-1}=0$, both give the same sum. Keeping only the best first cell for each last cell turns the double loop of Section 5 into a single pass.

7. The example of the statement, line by line

Take the bottom row $(-1,8,-4,8)$ of the example. It starts with $B_1=-1$. Next, $B_2=\max(8,-1+8)=8$: the run before has a negative sum, so the run starts afresh. Then $B_3=\max(-4,8-4)=4$ keeps the run, and $B_4=\max(8,4+8)=12$. The best segment of this row is $8-4+8=12$; crossing the $-4$ pays because the $8$ before it is larger. The anti-diagonal from the top row down to the left column reads $(3,-6,3)$ and gives $B=(3,-3,3)$: after the run $3-6$, whose sum is negative, the last $3$ starts afresh. The anti-diagonal $(1,7,8)$, from row $2$ of the right column down to row $4$, gives $B=(1,8,16)$. Doing the same for all $22$ lines, the best row is the third with $3+2+7+3=15$, the best column is the third with $3+5+7=15$, the best diagonal is the main diagonal with $7+8=15$, and the best anti-diagonal is the one with $1+7+8=16$. So the answer for the example is $16$, the statement's $8+7+1$ read in the other direction.

8. How large the sums can get

Every entry lies between $-500000$ and $499999$, and a line has at most $2000$ cells, so every segment sum lies between $-10^9$ and $999\,998\,000$. The values $B_t$ are even more limited from below: $B_t\ge x_t\ge-500000$, since the maximum that defines $B_t$ includes $x_t$ itself, and therefore $B_{t-1}+x_t\ge-10^6$. All these numbers fit into a signed 32-bit integer, whose largest value is $2^{31}-1=2147483647$. This guarantee holds for lines of up to $4294$ cells, since $4294\cdot499999$ is below $2^{31}-1$ and $4295\cdot499999$ is not.

9. Other ways to do it

For an arbitrary table, every exact method has to look at every cell: if all entries are $-1$, changing a single unseen entry to $1$ changes the answer from $-1$ to $1$. So for general tables the scan is optimal up to a constant factor. For a single line, older methods take $O(L^2)$ time with prefix sums or $O(L\log L)$ by divide and conquer. ^[2] Memory can be saved too: the generator delivers the table row by row, so one pass suffices if we keep one value $B$ for the current row and one for every column, diagonal and anti-diagonal, $5n-1$ values in all, plus the last $55$ terms of the generator. The published programs store the whole table instead, which keeps their scans simple; the one-pass version served as a check.

How the Code Works

The C++ program ^[7] starts in main with a size of $2000$ and the checkpoints switched on. parse_arguments accepts --skip-checkpoints and --size= followed by digits, and rejects anything else, or a size below $1$, with exit code $1$. run_checkpoints generates the first $100$ terms and requires $s_{10}=-393027$ and $s_{100}=86613$, the values of the statement; otherwise the exit code is $2$. Then main prints solve(size).

generate_sequence(total) returns a std::vector<int> in which index $k$ holds $s_k$; index $0$ is unused. It evaluates the cubic of Section 1 in long long, since $c_{55}$ exceeds 32 bits, and the lagged rule of Section 2 in int; its first loop stops at std::min(55, total), so even tables with fewer than $55$ cells work. In solve, the lambda at(r, c) returns entry $rn+c+1$ of the vector, the formula of Section 3.

Six loops follow: one for the rows, one for the columns and two for each diagonal family. A diagonal begins in its highest cell, in the top row or in the left column, so the diagonals start at $(0,c)$ for every $c$ and at $(r,0)$ for $r\ge1$, and step by $(1,1)$; the anti-diagonals start at $(0,c)$ and at $(r,n-1)$ for $r\ge1$, and step by $(1,-1)$. Thus each of the $6n-2$ lines of Section 4 is scanned exactly once; starting in the top row only would miss $n-1$ lines of each diagonal family. Before each line, current is set to std::numeric_limits<int>::min() / 4, which is $-536870912$, and kadane_extend(value, current) returns std::max(value, current + value), the rule of Section 6. At the first cell this yields $B_1=x_1$, and $-536870912-500000$ still fits easily into an int. best starts at the smallest int and keeps the largest value of current.

The Python and Java programs fix the size at $2000$, have no options or checkpoints, and scan the lines in the same order. Python starts each line and best at float('-inf'); since $-\infty+v=-\infty$, the first max returns the entry itself. Its integers are unbounded, but its loops are much slower: every visit of a cell calls the helper at for the entry and kadane_update, which calls max. Java uses a long array and Long.MIN_VALUE / 4, and reduces the cubic as (x % 1000000 + 1000000) % 1000000, a normalisation that changes nothing here because the cubic is positive.

The option --size is meant for small tests: parse_int_after_prefix does not check the range of its number, and above $46340$ the product size * size overflows int, which is undefined behaviour. ^[6] The default run is not affected.

Complexity and Verification

Generating the terms takes $n^2=4\,000\,000$ steps and the scan $4n^2=16\,000\,000$ updates, one per cell and family, so the time is $O(n^2)$, which by Section 9 is optimal up to a constant factor for arbitrary tables. The memory is $O(n^2)$ because all terms are kept: $4\,000\,001$ values of type int, about $16$ MB, in C++, and twice as much as long values in Java. In 64-bit CPython the list holds for each term an 8-byte reference to an integer object of $28$ bytes, about $144$ MB for four million terms; the whole Python process peaked at about $170$ MB. On a desktop computer the C++ program takes about a hundredth of a second, the Java program less than a tenth including its start, and Python about $2.5$ seconds.

The C++ program checks $s_{10}$ and $s_{100}$ before its main run; the example table of the statement, which does not come from the generator, is checked by none of the programs. For this article all three programs were run and print the same number. A separately written brute force that tries all $13\,341\,334\,000$ segments of the full table with prefix sums gives the same number, and so does a separately written one-pass program with $O(n)$ memory as in Section 9. Both also agree with the C++ program run with --size, which puts the first $n^2$ terms into an $n\times n$ table, for every size from $1$ to $120$ and for $150$, $200$, $257$, $300$ and $500$. For example, --size=4 gives $486722$, the bottom row $115343+19169$${}+123583+228627$ of the table of $s_1,\dots,s_{16}$, and --size=100 gives $8642499$. On the example of the statement, Kadane's rule agrees with a brute force on all $22$ lines and gives $16$, and the shifted rule of Section 2 holds for every $k$ from $56$ to $4\,000\,000$. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The reduction to $6n-2$ lines, the count of segments and the bounds on the sums are derived in this article.

Project Euler 149 — Maximum-sum Subsequence. The official statement gives the 4 × 4 example with the greatest sum 16 = 8 + 7 + 1 and the generator with s₁₀ = −393027 and s₁₀₀ = 86613, and asks, for the 2000 × 2000 table filled row by row, for the greatest sum of any number of adjacent entries in any direction: horizontal, vertical, diagonal or anti-diagonal.
Wikipedia — Maximum subarray problem. Kadane's algorithm keeps the largest sum of a subarray ending at the current position, current_sum = max(x, current_sum + x), runs in O(n) time and can be viewed as dynamic programming; some formulations also allow the empty subarray. Grenander, who proposed the problem in 1977, solved it in O(n²) time using prefix sums, Shamos then in O(n log n) by divide and conquer, and Kadane in O(n).
Wikipedia — Lagged Fibonacci generator. Such a generator computes Sₙ ≡ Sₙ₋ⱼ ⋆ Sₙ₋ₖ (mod m) with 0 < j < k; with addition as the operation ⋆ it is called additive. The pair j = 24, k = 55 is among the popular lags listed, with a reference to The Art of Computer Programming, volume 2.
Wikipedia — Row- and column-major order. In row-major order the consecutive elements of a row lie next to each other; with zero-based indices, the element in row r and column c of a table with C columns has the offset r · C + c.
Wikipedia — Tetrahedral number. The n-th tetrahedral number is the sum of the first n triangular numbers k(k + 1)/2 and equals n(n + 1)(n + 2)/6.
cppreference — Arithmetic operators: for integers the quotient is truncated towards zero and (a / b) * b + a % b == a, and signed integer overflow is undefined behaviour. Java Language Specification, §15.17.3: a remainder can be negative only if the dividend is negative. Python Language Reference, §6.7: the result of % has the sign of the second operand or is zero.
C++ — Euler149.cpp. The linked immutable C++ revision contains parse_arguments, generate_sequence, kadane_extend, solve and run_checkpoints. It is the implementation record for this article.

Problem 149 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

namespace {

struct Options {
    int size = 2000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--size=", options.size)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.size >= 1;
}

std::vector<int> generate_sequence(const int total) {
    std::vector<int> s(static_cast<std::size_t>(total + 1), 0);

    for (int k = 1; k <= std::min(55, total); ++k) {
        const long long kk = static_cast<long long>(k);
        const long long value = (100003LL - 200003LL * kk + 300007LL * kk * kk * kk) % 1000000LL;
        s[static_cast<std::size_t>(k)] = static_cast<int>(value) - 500000;
    }

    for (int k = 56; k <= total; ++k) {
        const int value = (s[static_cast<std::size_t>(k - 24)] + s[static_cast<std::size_t>(k - 55)] + 1000000) % 1000000;
        s[static_cast<std::size_t>(k)] = value - 500000;
    }

    return s;
}

int kadane_extend(const int value, const int current) {
    return std::max(value, current + value);
}

int solve(const int size) {
    const int total = size * size;
    const std::vector<int> s = generate_sequence(total);

    int best = std::numeric_limits<int>::min();

    auto at = [&](const int r, const int c) -> int {
        return s[static_cast<std::size_t>(r * size + c + 1)];
    };

    for (int r = 0; r < size; ++r) {
        int current = std::numeric_limits<int>::min() / 4;
        for (int c = 0; c < size; ++c) {
            current = kadane_extend(at(r, c), current);
            best = std::max(best, current);
        }
    }

    for (int c = 0; c < size; ++c) {
        int current = std::numeric_limits<int>::min() / 4;
        for (int r = 0; r < size; ++r) {
            current = kadane_extend(at(r, c), current);
            best = std::max(best, current);
        }
    }

    for (int start = 0; start < size; ++start) {
        int current = std::numeric_limits<int>::min() / 4;
        for (int r = 0, c = start; r < size && c < size; ++r, ++c) {
            current = kadane_extend(at(r, c), current);
            best = std::max(best, current);
        }
    }
    for (int start = 1; start < size; ++start) {
        int current = std::numeric_limits<int>::min() / 4;
        for (int r = start, c = 0; r < size && c < size; ++r, ++c) {
            current = kadane_extend(at(r, c), current);
            best = std::max(best, current);
        }
    }

    for (int start = 0; start < size; ++start) {
        int current = std::numeric_limits<int>::min() / 4;
        for (int r = 0, c = start; r < size && c >= 0; ++r, --c) {
            current = kadane_extend(at(r, c), current);
            best = std::max(best, current);
        }
    }
    for (int start = 1; start < size; ++start) {
        int current = std::numeric_limits<int>::min() / 4;
        for (int r = start, c = size - 1; r < size && c >= 0; ++r, --c) {
            current = kadane_extend(at(r, c), current);
            best = std::max(best, current);
        }
    }

    return best;
}

bool run_checkpoints() {
    const std::vector<int> s = generate_sequence(100);
    if (s[10] != -393027) {
        std::cerr << "Checkpoint failed for s10" << '\n';
        return false;
    }
    if (s[100] != 86613) {
        std::cerr << "Checkpoint failed for s100" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.size) << '\n';
    return 0;
}

Python

# Problem 149: Searching for a maximum-sum subsequence

def solve():
    size = 2000
    total = size * size
    s = [0] * (total + 1)
    for k in range(1, 56):
        s[k] = (100003 - 200003*k + 300007*k*k*k) % 1000000 - 500000
    for k in range(56, total + 1):
        s[k] = (s[k-24] + s[k-55] + 1000000) % 1000000 - 500000
    
    def at(r, c):
        return s[r * size + c + 1]
    
    best = float('-inf')
    
    # Kadane's algorithm
    def kadane_update(v, cur):
        return max(v, cur + v)
    
    # Rows
    for r in range(size):
        cur = float('-inf')
        for c in range(size):
            cur = kadane_update(at(r, c), cur)
            if cur > best: best = cur
    
    # Columns
    for c in range(size):
        cur = float('-inf')
        for r in range(size):
            cur = kadane_update(at(r, c), cur)
            if cur > best: best = cur
    
    # Diagonal \ starting from row 0
    for cs in range(size):
        cur = float('-inf')
        r, c = 0, cs
        while r < size and c < size:
            cur = kadane_update(at(r, c), cur)
            if cur > best: best = cur
            r += 1; c += 1
    # Diagonal \ starting from col 0
    for rs in range(1, size):
        cur = float('-inf')
        r, c = rs, 0
        while r < size and c < size:
            cur = kadane_update(at(r, c), cur)
            if cur > best: best = cur
            r += 1; c += 1
    
    # Anti-diagonal / starting from row 0
    for cs in range(size):
        cur = float('-inf')
        r, c = 0, cs
        while r < size and c >= 0:
            cur = kadane_update(at(r, c), cur)
            if cur > best: best = cur
            r += 1; c -= 1
    # Anti-diagonal / starting from col size-1
    for rs in range(1, size):
        cur = float('-inf')
        r, c = rs, size - 1
        while r < size and c >= 0:
            cur = kadane_update(at(r, c), cur)
            if cur > best: best = cur
            r += 1; c -= 1
    
    print(best)

solve()

Java

public class Euler149 {
    public static void main(String[] args) {
        int size = 2000, total = size * size;
        long[] s = new long[total + 1];
        for (int k = 1; k <= 55; k++)
            s[k] = ((100003L - 200003L * k + 300007L * k * k * k) % 1000000 + 1000000) % 1000000 - 500000;
        for (int k = 56; k <= total; k++)
            s[k] = (s[k - 24] + s[k - 55] + 1000000) % 1000000 - 500000;
        long best = Long.MIN_VALUE;
        // Rows
        for (int r = 0; r < size; r++) {
            long cur = Long.MIN_VALUE / 4;
            for (int c = 0; c < size; c++) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        // Cols
        for (int c = 0; c < size; c++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = 0; r < size; r++) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        // Diag \
        for (int cs = 0; cs < size; cs++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = 0, c = cs; r < size && c < size; r++, c++) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        for (int rs = 1; rs < size; rs++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = rs, c = 0; r < size && c < size; r++, c++) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        // Diag /
        for (int cs = 0; cs < size; cs++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = 0, c = cs; r < size && c >= 0; r++, c--) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        for (int rs = 1; rs < size; rs++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = rs, c = size - 1; r < size && c >= 0; r++, c--) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        System.out.println(best);
    }
}