Maximum Sum Submatrix – Solution Using 2D Prefix Sum

Problem Description

Given an N × M integer matrix, select a contiguous rectangular sub‑matrix (called the “maximum‑sum submatrix”) such that the sum of all numbers inside it is as large as possible.

Input

The first line contains two integers N,M (1 ≤ N,M ≤ 10). The next N lines each contain M integers in the range [-1000, 1000], separated by a single space.

Output

Output a single integer – the sum of the selected maximum‑sum sub‑matrix.

Example

3 4
-3 5 -1 5
2 4 -2 4
-1 3 -1 3

Output:

20

Solution Idea

Representing a Sub‑matrix

A sub‑matrix can be uniquely defined by four parameters: top row a , bottom row b , left column c , and right column d . Enumerating all possible a,b,c,d values with four nested for loops yields every candidate rectangle.

Brute‑Force Method

The naïve approach sums every element of each candidate sub‑matrix, leading to six nested loops and O(N³ M³) time, which is acceptable only because N,M ≤ 10.

for a in range(n):
    for b in range(a, n):
        for c in range(m):
            for d in range(c, m):
                submat_sum = 0
                for i in range(a, b+1):
                    for j in range(c, d+1):
                        submat_sum += mat[i][j]
                ans = max(submat_sum, ans)

2D Prefix‑Sum Optimization

To compute any sub‑matrix sum in O(1), build a 2‑dimensional prefix‑sum matrix pre_sum_mat where pre_sum_mat[i][j] stores the sum of the rectangle from (0,0) to (i‑1,j‑1) (exclusive on the bottom‑right). The sum of a rectangle [a:b+1][c:d+1] is then:

pre_sum_mat[b+1][d+1] + pre_sum_mat[a][c] - pre_sum_mat[b+1][c] - pre_sum_mat[a][d+1]

Using this formula inside the four‑parameter enumeration reduces the inner two loops to O(1), giving overall O(N² M²) time.

Building the Prefix‑Sum Matrix

pre_sum_mat = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        pre_sum_mat[i][j] = (
            pre_sum_mat[i-1][j] +
            pre_sum_mat[i][j-1] -
            pre_sum_mat[i-1][j-1] +
            mat[i-1][j-1]
        )

Complete Python Code

from math import inf

n, m = map(int, input().split())
mat = []
for _ in range(n):
    row = list(map(int, input().split()))
    mat.append(row)

# Build 2D prefix sum array
pre_sum_mat = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        pre_sum_mat[i][j] = (
            pre_sum_mat[i-1][j] +
            pre_sum_mat[i][j-1] -
            pre_sum_mat[i-1][j-1] +
            mat[i-1][j-1]
        )

ans = -inf
# Enumerate top row a
for a in range(n):
    # Enumerate bottom row b
    for b in range(a, n):
        # Enumerate left column c
        for c in range(m):
            # Enumerate right column d
            for d in range(c, m):
                submat_sum = (
                    pre_sum_mat[b+1][d+1] +
                    pre_sum_mat[a][c] -
                    pre_sum_mat[b+1][c] -
                    pre_sum_mat[a][d+1]
                )
                ans = max(submat_sum, ans)

print(ans)

Time and Space Complexity

Time complexity: O(N² M²) due to the four‑parameter enumeration, each sub‑matrix sum computed in O(1). Space complexity: O(N M) for the original matrix plus O((N+1)(M+1)) for the prefix‑sum matrix.