Maximum sum rectangle in a 2D matrix.

Problem Statement

Given a 2D matrix of integers, find the maximum sum rectangle within the matrix using the prefix sum technique.

Example
Input:

matrix = [
[ 1, 2, -1, -4, -20],
[-8, -3, 4, 2, 1],
[ 3, 8, 10, 1, 3],
[-4, -1, 1, 7, -6]
]
Output:

29

Approach (2D Prefix Sum + Submatrix Sum Calculation)

Key Idea:
Construct a 2D prefix sum matrix, where prefix[i][j] represents the sum of all elements in the submatrix from (0,0) to (i,j).

For any submatrix (r1, c1) to (r2, c2), the sum can be found in O(1) using the prefix matrix:

submatrix_sum = prefix[r2][c2]
- prefix[r1-1][c2]
- prefix[r2][c1-1]
+ prefix[r1-1][c1-1]
Iterate over all pairs of (r1, r2) and (c1, c2) to find the maximum sum submatrix.

Steps:

1. Build a 2D prefix sum matrix in O(rows × cols).
2. For every pair of top-left (r1, c1) and bottom-right (r2, c2) corners, calculate the submatrix sum using the prefix matrix.
3. Keep track of the maximum sum found.

C++ Code (Prefix Sum)

#include <bits/stdc++.h>
using namespace std;

int maxSumRectanglePrefix(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();

    // Build prefix sum matrix
    vector<vector<int>> prefix(rows + 1, vector<int>(cols + 1, 0));
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            prefix[i][j] = matrix[i-1][j-1] 
                         + prefix[i-1][j] 
                         + prefix[i][j-1] 
                         - prefix[i-1][j-1];
        }
    }

    int maxSum = INT_MIN;

    // Iterate over all submatrices
    for (int r1 = 1; r1 <= rows; r1++) {
        for (int c1 = 1; c1 <= cols; c1++) {
            for (int r2 = r1; r2 <= rows; r2++) {
                for (int c2 = c1; c2 <= cols; c2++) {
                    int currSum = prefix[r2][c2]
                                - prefix[r1-1][c2]
                                - prefix[r2][c1-1]
                                + prefix[r1-1][c1-1];
                    maxSum = max(maxSum, currSum);
                }
            }
        }
    }
    return maxSum;
}

int main() {
    vector<vector<int>> matrix = {
        { 1,  2, -1, -4, -20},
        {-8, -3,  4,  2,   1},
        { 3,  8, 10,  1,   3},
        {-4, -1,  1,  7,  -6}
    };
    cout << "Maximum Sum Rectangle = " << maxSumRectanglePrefix(matrix) << endl;
    return 0;
}

Complexity Analysis

Time Complexity: O(rows² × cols²) (because we consider all submatrices).

Space Complexity: O(rows × cols) (for the prefix matrix).

Open Source Contribution

I am building an open-source repository of DSA solutions in C++, organized algorithm-wise for easier learning.
Feel free to explore, star ⭐, and contribute to my repository:
👉 DSA in C++ – GitHub Repository