Maximum Sum Submatrix

Tags

Maximum Sum Submatrix

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

Given a 2D matrix of integers and a positive integer size, find the size x size submatrix that has the greatest sum of its elements. Return the maximum sum.

Intuition

Naively summing every possible size x size submatrix takes O(rows * cols * size^2). We can precompute a prefix sum matrix so that the sum of any rectangular sub-region can be calculated in O(1) using inclusion-exclusion. Then we simply evaluate every valid top-left corner in O(1) each.

Approach

  1. Build a prefix sum matrix P where P[i][j] = sum of all elements in matrix[0..i-1][0..j-1].
    • P[i][j] = matrix[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]
  2. For every valid bottom-right corner (r, c) of a size x size submatrix (where r ranges from size to rows and c from size to cols):
    • Compute the submatrix sum: P[r][c] - P[r-size][c] - P[r][c-size] + P[r-size][c-size]
    • Track the maximum.
  3. Return the maximum sum found.

Pseudocode

function maxSumSubmatrix(matrix, size):
    rows = length(matrix)
    cols = length(matrix[0])

    // Build prefix sum matrix (1-indexed)
    P = 2D array of size (rows+1) x (cols+1), filled with 0
    for i from 1 to rows:
        for j from 1 to cols:
            P[i][j] = matrix[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

    maxSum = -INFINITY
    for r from size to rows:
        for c from size to cols:
            total = P[r][c] - P[r-size][c] - P[r][c-size] + P[r-size][c-size]
            maxSum = max(maxSum, total)

    return maxSum

Time & Space Complexity

MeasureComplexityJustification
TimeO(rows * cols)Building the prefix sum is O(rows * cols); evaluating each submatrix is O(1) and there are O(rows * cols) positions
SpaceO(rows * cols)For the prefix sum matrix

Key Insights

  • The inclusion-exclusion principle on the prefix sum matrix is the key identity: sum(r1,c1,r2,c2) = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1].
  • This technique generalizes to any fixed-size rectangular submatrix, not just squares.
  • The prefix sum matrix uses 1-based indexing (with a padding row/column of zeros) to avoid boundary checks.
  • For the variant where size is not fixed and we want the max-sum rectangle of any size, Kadane's algorithm extended to 2D gives O(rows^2 * cols).

Edge Cases

  • Matrix is exactly size x size: only one submatrix exists; return the total sum of the matrix.
  • All negative values: the answer is the submatrix with the least negative sum.
  • size is 1: reduces to finding the single maximum element.
  • Single row or single column matrix: the problem reduces to a 1D sliding window of length size.

Linked mentions