Overview

Given an \(N \times M\) grid, the problem asks to select one rectangular region and maximize the sum of values within it. This can be solved efficiently by extending the 1D “maximum subarray sum (Kadane’s algorithm)” to 2D.

Analysis

Naive Approach

A rectangular region is determined by 4 values \((r_1, r_2, c_1, c_2)\). Trying all combinations gives \(O(N^2 M^2)\) possibilities, and if computing the sum of each rectangle takes \(O(NM)\), the total becomes \(O(N^3 M^3)\), which is far too slow. Even using prefix sums to compute each rectangle’s sum in \(O(1)\), it’s still \(O(N^2 M^2)\), which for \(N = M = 500\) amounts to approximately \(6.25 \times 10^{10}\) operations — this will also TLE.

Key Insight: Reduction to a 1D Problem

Let’s recall the 1D maximum subarray sum problem. Given an array of length \(M\), the maximum sum of a contiguous subarray can be found in \(O(M)\) using Kadane’s algorithm.

A 2D rectangle is determined by the “row range \((r_1, r_2)\)” and “column range \((c_1, c_2)\)”. If we fix the row range \((r_1, r_2)\), for each column \(j\) we can compute the sum from row \(r_1\) to row \(r_2\): \(\text{col\_sum}[j] = \sum_{i=r_1}^{r_2} A_{i,j}\). Then, choosing the optimal column range \((c_1, c_2)\) reduces to a 1D maximum subarray sum problem on the array \(\text{col\_sum}\).

Concrete Example

For example, consider the following \(3 \times 4\) grid with \(r_1 = 1, r_2 = 2\) fixed:

	Col 1	Col 2	Col 3	Col 4
Row 1	1	-3	5	2
Row 2	4	1	-2	3

We get \(\text{col\_sum} = [5, -2, 3, 5]\), and applying Kadane’s algorithm yields a maximum subarray sum \(= 11\) (the entire array).

Algorithm

1. For every row starting position \(r_1 = 0, 1, \ldots, N-1\):
   • Initialize an array \(\text{col\_sum}\) of length \(M\) to \([0, 0, \ldots, 0]\).
   • For \(r_2 = r_1, r_1+1, \ldots, N-1\) in order:
     • For each column \(j\), add \(A[r_2][j]\) to \(\text{col\_sum}[j]\) (adding one more row).
     • Run Kadane’s algorithm on \(\text{col\_sum}\) to find the maximum subarray sum.
     • Update the overall answer.
2. After trying all pairs \((r_1, r_2)\), output the answer.

Kadane’s algorithm scans the array from left to right while maintaining “the current subarray sum \(\text{current}\)”. At each element, update \(\text{current} = \max(a_j, \text{current} + a_j)\), and the maximum value encountered along the way is the answer.

Complexity

• Time complexity: \(O(N^2 \times M)\)
  • There are \(O(N^2)\) row pairs \((r_1, r_2)\), and for each pair Kadane’s algorithm takes \(O(M)\).
  • For \(N = M = 500\), this is approximately \(6.25 \times 10^7\) operations, which is sufficiently fast.
• Space complexity: \(O(NM)\) (storing the input) + \(O(M)\) (the \(\text{col\_sum}\) array)

Implementation Notes

• By adding \(A[r_2][j]\) to \(\text{col\_sum}[j]\) each time \(r_2\) is incremented by one, we avoid recomputing the column sums from scratch each time (incremental update).

• The initial value of the answer should be \(-\infty\). Since at least one cell must be selected, initializing to \(0\) would be incorrect when all elements are negative.

• In Python, using sys.stdin.read() to read all input at once speeds up input processing.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    A = []
    for i in range(N):
        row = [int(input_data[idx + j]) for j in range(M)]
        idx += M
        A.append(row)
    
    # Prefix sum over rows for each column
    # For each pair of rows (r1, r2), compress into 1D array and apply Kadane's algorithm
    # O(N^2 * M)
    
    ans = float('-inf')
    
    for r1 in range(N):
        col_sum = [0] * M
        for r2 in range(r1, N):
            for j in range(M):
                col_sum[j] += A[r2][j]
            # Kadane's algorithm on col_sum
            current = col_sum[0]
            best = col_sum[0]
            for j in range(1, M):
                current = max(col_sum[j], current + col_sum[j])
                if current > best:
                    best = current
            if best > ans:
                ans = best
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.