Overview

Given an \(N \times M\) integer grid, the problem asks to select a “rectangle containing one or more cells” and maximize its sum. We efficiently solve the 2D maximum subarray problem (maximum rectangular subarray sum).

Analysis

Key Insight

A rectangle can be compressed into “the sum of each column” by fixing the top row \(top\) and bottom row \(bottom\).

For example, fixing \(top=2, bottom=4\), for column \(j\): [ Bj = \sum{i=top}^{bottom} A_{i,j} ] This creates a 1D array \(B\). Then, the sum of the rectangle over column range \([c_1, c_2]\) is [ \sum_{j=c_1}^{c_2} B_j ] which reduces to the “maximum contiguous subarray sum (maximum subarray problem)” on a 1D array.

Why the Naive Solution Is Too Slow

A rectangle requires choosing 4 parameters \((r_1,r_2,c_1,c_2)\), so the number of rectangles is \(O(N^2 M^2)\). Computing the sum of each rectangle adds further cost, making it far too slow for \(N,M \le 500\).

Solution Strategy

• Enumerate all pairs of rows \((top, bottom)\) (or all pairs of columns \((left, right)\))
• For each pair, compress into a 1D array along the other dimension
• Use Kadane’s algorithm (maximum subarray sum) to update the maximum value

Furthermore, choosing the smaller of \(N\) and \(M\) as the “dimension to enumerate pairs over” minimizes the computation (the code branches on this as well).

Algorithm

Below explains the case where \(N \le M\) (fixing row pairs). When \(N > M\), the same procedure is applied with rows and columns swapped.

1. Initialize the answer ans to a sufficiently small value (negative infinity). ※ Since an empty rectangle cannot be selected, even if all elements are negative, we must select the maximum (= least negative) value.
2. Iterate the top row top from \(0..N-1\)
3. Initialize temp[j] (the vertical sum of column \(j\) from row \(top\) to \(bottom\)) to 0
4. Iterate the bottom row bottom from top..N-1
   • Update temp[j] += A[bottom][j] to obtain the compressed array for rows \(top..bottom\)
   • Run Kadane’s algorithm on temp and update ans with the maximum contiguous subarray sum

Kadane’s algorithm (1D maximum subarray sum) works as follows: - Let cur be “the maximum subarray sum ending at the current position” - For the next value v: [ cur = \max(v,\ cur+v) ] - At each step, update ans = max(ans, cur)

In the code, for optimization, this is implemented equivalently as if cur > 0: cur += v else: cur = v.

Complexity

Let \(K=\min(N,M)\) be the smaller dimension and \(L=\max(N,M)\) be the larger dimension.

• Time complexity: \(O(K^2 \cdot L)\) (\(O(K^2)\) pairs, each with Kadane’s algorithm in \(O(L)\))
• Space complexity: \(O(L)\) (only the compression array temp)

Implementation Details

• Dimension swapping (branching): If \(N \le M\), fix row pairs; otherwise, fix column pairs to achieve \(O(\min(N,M)^2 \max(N,M))\).

• Handling all-negative cases: ans is initialized to a very small value, and Kadane’s update always selects at least one element (empty selection is not allowed).

• Fast I/O: Using sys.stdin.buffer.read().split() to make it feasible even in Python.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    vals = list(map(int, data))
    N, M = vals[0], vals[1]
    idx = 2
    A = [vals[idx + i*M: idx + (i+1)*M] for i in range(N)]

    NEG_INF = -10**30
    ans = NEG_INF

    if N <= M:
        C = M
        for top in range(N):
            temp = [0] * C
            for bottom in range(top, N):
                row = A[bottom]
                t = temp
                cur = 0
                for j in range(C):
                    v = t[j] + row[j]
                    t[j] = v
                    if cur > 0:
                        cur += v
                    else:
                        cur = v
                    if cur > ans:
                        ans = cur
    else:
        R = N
        for left in range(M):
            temp = [0] * R
            for right in range(left, M):
                t = temp
                cur = 0
                rr = right
                for i in range(R):
                    v = t[i] + A[i][rr]
                    t[i] = v
                    if cur > 0:
                        cur += v
                    else:
                        cur = v
                    if cur > ans:
                        ans = cur

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.