Overview

This problem is the maximum subarray rectangle sum problem, where we need to find the rectangular region with the maximum sum of elements from a given 2D grid.

Analysis

In a naive approach, trying all possible rectangular regions (all combinations of top-left and bottom-right coordinates) would result in a time complexity of \(O(N^2M^2)\). With the constraints \(N, M \leq 500\), this requires up to approximately \(500^4 = 62,500,000,000\) computations, which is impractical.

The key observation is that when we fix the range of rows, the column direction can be reduced to the 1D maximum subarray sum problem. By fixing the row range \([top, bottom]\), we can compute the sum of each column, treating the cumulative column sums within that row range as a 1D array. By applying Kadane’s algorithm to this 1D array, we can find the maximum subarray sum in \(O(M)\).

Algorithm

1. Loop the top row \(top\) from \(0\) to \(N-1\)
2. For each \(top\), loop the bottom row \(bottom\) from \(top\) to \(N-1\)
3. For each row range \([top, bottom]\), update the array \(temp\) that holds the sum of each column (each time \(bottom\) moves one row down, add the corresponding row’s values to \(temp\))
4. Apply Kadane’s algorithm to the updated \(temp\) array to compute the maximum subarray sum
   • Update the current subarray sum with \(current = \max(num, current + num)\)
   • Update the overall maximum with \(best = \max(best, current)\)
5. The answer is the maximum subarray sum obtained across all row ranges

Complexity

• Time complexity: \(O(N^2M)\)
  • The outer double loop is \(O(N^2)\), and the inner Kadane’s algorithm is \(O(M)\)
• Space complexity: \(O(M)\)
  • The size of the array \(temp\) that holds the column-direction sums is \(M\)

Implementation Notes

• For each fixed row range, the \(temp\) array is reused to efficiently compute the cumulative column sums

• When applying Kadane’s algorithm, by initializing \(current\) and \(best\) to a sufficiently small negative value, it works correctly even when all elements are negative

• Pay attention to the range of input values, and set the initial value of \(ans\) to a sufficiently small value such as \(-10^{18}\)

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    grid = []
    for i in range(n):
        row = []
        for j in range(m):
            row.append(int(next(it)))
        grid.append(row)
    
    ans = -10**18
    for top in range(n):
        temp = [0] * m
        for bottom in range(top, n):
            for col in range(m):
                temp[col] += grid[bottom][col]
            current = 0
            best = -10**18
            for num in temp:
                current = max(num, current + num)
                best = max(best, current)
            ans = max(ans, best)
    
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.