Maximum Sum Rectangle in 2D Matrix

Problem Statement

You are given a 2D matrix matrix of size R × C containing integers (positive, negative, or zero).

Your task is to find the maximum sum rectangle (submatrix) within the given matrix.

A rectangle can span any contiguous rows and columns.

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

Explanation
Maximum sum rectangle:

[
  [-3,  4,  2],
  [ 8, 10,  1],
  [-1,  1,  7]
]

Sum = 29

Why This Problem Is Important

• Extension of Kadane’s Algorithm
• Frequently asked matrix problem
• Tests 2D → 1D reduction
• Used in image processing & data analysis
• Common in FAANG interviews

Approaches Overview

Approach 1: Brute Force (All Rectangles)

Idea

Try every possible rectangle using four loops and calculate its sum.

Algorithm

1. Choose top row
2. Choose bottom row
3. Choose left column
4. Choose right column
5. Calculate sum of the rectangle
6. Track maximum sum

Time & Space Complexity

• Time: O(n⁶)
• Space: O(1)

 C Implementation

#include 
#include 

int main() {
    int mat[4][5] = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };

    int R = 4, C = 5;
    int maxSum = INT_MIN;

    for(int r1 = 0; r1 < R; r1++) {
        for(int r2 = r1; r2 < R; r2++) {
            for(int c1 = 0; c1 < C; c1++) {
                for(int c2 = c1; c2 < C; c2++) {
                    int sum = 0;
                    for(int i = r1; i <= r2; i++) {
                        for(int j = c1; j <= c2; j++) {
                            sum += mat[i][j];
                        }
                    }
                    if(sum > maxSum) maxSum = sum;
                }
            }
        }
    }

    printf("%d", maxSum);
    return 0;
}

Output

29

 C++ Implementation

#include 
#include 
using namespace std;

int main() {
    int mat[4][5] = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };

    int R = 4, C = 5;
    int maxSum = INT_MIN;

    for(int r1 = 0; r1 < R; r1++) {
        for(int r2 = r1; r2 < R; r2++) {
            for(int c1 = 0; c1 < C; c1++) {
                for(int c2 = c1; c2 < C; c2++) {
                    int sum = 0;
                    for(int i = r1; i <= r2; i++) {
                        for(int j = c1; j <= c2; j++) {
                            sum += mat[i][j];
                        }
                    }
                    maxSum = max(maxSum, sum);
                }
            }
        }
    }

    cout << maxSum;
    return 0;
}

Output

29

Java Implementation

public class MaxSumRectangleBrute {
    public static void main(String[] args) {
        int[][] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };

        int R = 4, C = 5;
        int maxSum = Integer.MIN_VALUE;

        for(int r1 = 0; r1 < R; r1++) {
            for(int r2 = r1; r2 < R; r2++) {
                for(int c1 = 0; c1 < C; c1++) {
                    for(int c2 = c1; c2 < C; c2++) {
                        int sum = 0;
                        for(int i = r1; i <= r2; i++) {
                            for(int j = c1; j <= c2; j++) {
                                sum += mat[i][j];
                            }
                        }
                        maxSum = Math.max(maxSum, sum);
                    }
                }
            }
        }

        System.out.println(maxSum);
    }
}

Output

29

Python Implementation

mat = [
    [1,2,-1,-4,-20],
    [-8,-3,4,2,1],
    [3,8,10,1,3],
    [-4,-1,1,7,-6]
]

R, C = len(mat), len(mat[0])
maxSum = float('-inf')

for r1 in range(R):
    for r2 in range(r1, R):
        for c1 in range(C):
            for c2 in range(c1, C):
                s = 0
                for i in range(r1, r2 + 1):
                    for j in range(c1, c2 + 1):
                        s += mat[i][j]
                maxSum = max(maxSum, s)

print(maxSum)

Output

29

JavaScript Implementation

let mat = [
    [1,2,-1,-4,-20],
    [-8,-3,4,2,1],
    [3,8,10,1,3],
    [-4,-1,1,7,-6]
];

let R = mat.length, C = mat[0].length;
let maxSum = -Infinity;

for (let r1 = 0; r1 < R; r1++) {
    for (let r2 = r1; r2 < R; r2++) {
        for (let c1 = 0; c1 < C; c1++) {
            for (let c2 = c1; c2 < C; c2++) {
                let sum = 0;
                for (let i = r1; i <= r2; i++) {
                    for (let j = c1; j <= c2; j++) {
                        sum += mat[i][j];
                    }
                }
                maxSum = Math.max(maxSum, sum);
            }
        }
    }
}

console.log(maxSum);

Output

29

C# Implementation

using System;

class Program {
    static void Main() {
        int[,] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };

        int R = 4, C = 5;
        int maxSum = int.MinValue;

        for(int r1 = 0; r1 < R; r1++) {
            for(int r2 = r1; r2 < R; r2++) {
                for(int c1 = 0; c1 < C; c1++) {
                    for(int c2 = c1; c2 < C; c2++) {
                        int sum = 0;
                        for(int i = r1; i <= r2; i++) {
                            for(int j = c1; j <= c2; j++) {
                                sum += mat[i, j];
                            }
                        }
                        maxSum = Math.Max(maxSum, sum);
                    }
                }
            }
        }

        Console.WriteLine(maxSum);
    }
}

Output

29

Approach 2: Prefix Sum (2D)

Idea

Precompute prefix sum matrix to calculate any rectangle sum in O(1).

Algorithm

1. Build prefix sum matrix
2. Iterate over all possible rectangles
3. Use prefix sum formula to compute rectangle sum
4. Update maximum sum

Time & Space Complexity

• Time: O(n⁴)
• Space: O(n²)

C Implementation

#include 
#include 

int main() {
    int mat[4][5] = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };

    int R = 4, C = 5;
    int prefix[4][5];

    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            prefix[i][j] = mat[i][j]
                + (i > 0 ? prefix[i-1][j] : 0)
                + (j > 0 ? prefix[i][j-1] : 0)
                - (i > 0 && j > 0 ? prefix[i-1][j-1] : 0);
        }
    }

    int maxSum = INT_MIN;

    for(int r1 = 0; r1 < R; r1++) {
        for(int r2 = r1; r2 < R; r2++) {
            for(int c1 = 0; c1 < C; c1++) {
                for(int c2 = c1; c2 < C; c2++) {
                    int sum = prefix[r2][c2]
                        - (r1 > 0 ? prefix[r1-1][c2] : 0)
                        - (c1 > 0 ? prefix[r2][c1-1] : 0)
                        + (r1 > 0 && c1 > 0 ? prefix[r1-1][c1-1] : 0);
                    if(sum > maxSum) maxSum = sum;
                }
            }
        }
    }

    printf("%d", maxSum);
    return 0;
}

Output

29

C++ Implementation

#include 
#include 
using namespace std;

int main() {
    int mat[4][5] = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };

    int R = 4, C = 5;
    int prefix[4][5];

    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            prefix[i][j] = mat[i][j]
                + (i > 0 ? prefix[i-1][j] : 0)
                + (j > 0 ? prefix[i][j-1] : 0)
                - (i > 0 && j > 0 ? prefix[i-1][j-1] : 0);
        }
    }

    int maxSum = INT_MIN;

    for(int r1 = 0; r1 < R; r1++) {
        for(int r2 = r1; r2 < R; r2++) {
            for(int c1 = 0; c1 < C; c1++) {
                for(int c2 = c1; c2 < C; c2++) {
                    int sum = prefix[r2][c2]
                        - (r1 > 0 ? prefix[r1-1][c2] : 0)
                        - (c1 > 0 ? prefix[r2][c1-1] : 0)
                        + (r1 > 0 && c1 > 0 ? prefix[r1-1][c1-1] : 0);
                    maxSum = max(maxSum, sum);
                }
            }
        }
    }

    cout << maxSum;
    return 0;
}

Output

29

Java Implementation

public class MaxSumRectanglePrefix {
    public static void main(String[] args) {
        int[][] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };

        int R = 4, C = 5;
        int[][] prefix = new int[R][C];

        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                prefix[i][j] = mat[i][j]
                        + (i > 0 ? prefix[i-1][j] : 0)
                        + (j > 0 ? prefix[i][j-1] : 0)
                        - (i > 0 && j > 0 ? prefix[i-1][j-1] : 0);
            }
        }

        int maxSum = Integer.MIN_VALUE;

        for(int r1 = 0; r1 < R; r1++) {
            for(int r2 = r1; r2 < R; r2++) {
                for(int c1 = 0; c1 < C; c1++) {
                    for(int c2 = c1; c2 < C; c2++) {
                        int sum = prefix[r2][c2]
                                - (r1 > 0 ? prefix[r1-1][c2] : 0)
                                - (c1 > 0 ? prefix[r2][c1-1] : 0)
                                + (r1 > 0 && c1 > 0 ? prefix[r1-1][c1-1] : 0);
                        maxSum = Math.max(maxSum, sum);
                    }
                }
            }
        }

        System.out.println(maxSum);
    }
}

Output

29

Python Implementation

mat = [
    [1,2,-1,-4,-20],
    [-8,-3,4,2,1],
    [3,8,10,1,3],
    [-4,-1,1,7,-6]
]

R, C = len(mat), len(mat[0])
prefix = [[0]*C for _ in range(R)]

for i in range(R):
    for j in range(C):
        prefix[i][j] = mat[i][j] \
            + (prefix[i-1][j] if i > 0 else 0) \
            + (prefix[i][j-1] if j > 0 else 0) \
            - (prefix[i-1][j-1] if i > 0 and j > 0 else 0)

maxSum = float('-inf')

for r1 in range(R):
    for r2 in range(r1, R):
        for c1 in range(C):
            for c2 in range(c1, C):
                s = prefix[r2][c2] \
                    - (prefix[r1-1][c2] if r1 > 0 else 0) \
                    - (prefix[r2][c1-1] if c1 > 0 else 0) \
                    + (prefix[r1-1][c1-1] if r1 > 0 and c1 > 0 else 0)
                maxSum = max(maxSum, s)

print(maxSum)

Output

29

JavaScript Implementation

let mat = [
    [1,2,-1,-4,-20],
    [-8,-3,4,2,1],
    [3,8,10,1,3],
    [-4,-1,1,7,-6]
];

let R = mat.length, C = mat[0].length;
let prefix = Array.from({length: R}, () => Array(C).fill(0));

for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
        prefix[i][j] = mat[i][j]
            + (i > 0 ? prefix[i-1][j] : 0)
            + (j > 0 ? prefix[i][j-1] : 0)
            - (i > 0 && j > 0 ? prefix[i-1][j-1] : 0);
    }
}

let maxSum = -Infinity;

for (let r1 = 0; r1 < R; r1++) {
    for (let r2 = r1; r2 < R; r2++) {
        for (let c1 = 0; c1 < C; c1++) {
            for (let c2 = c1; c2 < C; c2++) {
                let sum = prefix[r2][c2]
                    - (r1 > 0 ? prefix[r1-1][c2] : 0)
                    - (c1 > 0 ? prefix[r2][c1-1] : 0)
                    + (r1 > 0 && c1 > 0 ? prefix[r1-1][c1-1] : 0);
                maxSum = Math.max(maxSum, sum);
            }
        }
    }
}

console.log(maxSum);

Output

29

C# Implementation

using System;

class Program {
    static void Main() {
        int[,] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };

        int R = 4, C = 5;
        int[,] prefix = new int[R, C];

        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                prefix[i, j] = mat[i, j]
                    + (i > 0 ? prefix[i-1, j] : 0)
                    + (j > 0 ? prefix[i, j-1] : 0)
                    - (i > 0 && j > 0 ? prefix[i-1, j-1] : 0);
            }
        }

        int maxSum = int.MinValue;

        for(int r1 = 0; r1 < R; r1++) {
            for(int r2 = r1; r2 < R; r2++) {
                for(int c1 = 0; c1 < C; c1++) {
                    for(int c2 = c1; c2 < C; c2++) {
                        int sum = prefix[r2, c2]
                            - (r1 > 0 ? prefix[r1-1, c2] : 0)
                            - (c1 > 0 ? prefix[r2, c1-1] : 0)
                            + (r1 > 0 && c1 > 0 ? prefix[r1-1, c1-1] : 0);
                        maxSum = Math.Max(maxSum, sum);
                    }
                }
            }
        }

        Console.WriteLine(maxSum);
    }
}

Output

29

Approach 3: Kadane’s Algorithm (Optimal)

Idea

• Fix left and right columns
• Compress rows into a 1D array
• Apply Kadane’s Algorithm on row sums

Algorithm

1. Fix left column
2. Initialize temp array with zeros
3. For each right column:
   • Add column values to temp
   • Apply Kadane on temp
4. Update maximum sum

Time & Space Complexity

• Time: O(R² × C)
• Space: O(C)

Kadane Helper (1D)

kadane(arr):
    maxSoFar = arr[0]
    currMax = arr[0]
    for i from 1 to n:
        currMax = max(arr[i], currMax + arr[i])
        maxSoFar = max(maxSoFar, currMax)
    return maxSoFar

C Implementation

#include 
#include 

int kadane(int arr[], int n) {
    int maxSoFar = arr[0], curr = arr[0];
    for(int i = 1; i < n; i++) {
        if(curr + arr[i] > arr[i])
            curr = curr + arr[i];
        else
            curr = arr[i];

        if(curr > maxSoFar)
            maxSoFar = curr;
    }
    return maxSoFar;
}

int main() {
    int mat[4][5] = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };

    int R = 4, C = 5;
    int maxSum = INT_MIN;

    for(int left = 0; left < C; left++) {
        int temp[4] = {0};

        for(int right = left; right < C; right++) {
            for(int i = 0; i < R; i++)
                temp[i] += mat[i][right];

            int sum = kadane(temp, R);
            if(sum > maxSum) maxSum = sum;
        }
    }

    printf("%d", maxSum);
    return 0;
}

Output

29

C++ Implementation

#include 
#include 
using namespace std;

int kadane(int arr[], int n) {
    int maxSum = arr[0], curr = arr[0];
    for(int i = 1; i < n; i++) {
        curr = max(arr[i], curr + arr[i]);
        maxSum = max(maxSum, curr);
    }
    return maxSum;
}

int main() {
    int mat[4][5] = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };

    int R = 4, C = 5;
    int maxSum = INT_MIN;

    for(int left = 0; left < C; left++) {
        int temp[4] = {0};

        for(int right = left; right < C; right++) {
            for(int i = 0; i < R; i++)
                temp[i] += mat[i][right];

            maxSum = max(maxSum, kadane(temp, R));
        }
    }

    cout << maxSum;
    return 0;
}

Output

29

Java Implementation

public class MaxSumRectangleKadane {

    static int kadane(int[] arr) {
        int max = arr[0], curr = arr[0];
        for(int i = 1; i < arr.length; i++) {
            curr = Math.max(arr[i], curr + arr[i]);
            max = Math.max(max, curr);
        }
        return max;
    }

    public static void main(String[] args) {
        int[][] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };

        int R = 4, C = 5;
        int maxSum = Integer.MIN_VALUE;

        for(int left = 0; left < C; left++) {
            int[] temp = new int[R];

            for(int right = left; right < C; right++) {
                for(int i = 0; i < R; i++)
                    temp[i] += mat[i][right];

                maxSum = Math.max(maxSum, kadane(temp));
            }
        }

        System.out.println(maxSum);
    }
}

Output

29

Python Implementation

def kadane(arr):
    max_sum = curr = arr[0]
    for x in arr[1:]:
        curr = max(x, curr + x)
        max_sum = max(max_sum, curr)
    return max_sum

mat = [
    [1,2,-1,-4,-20],
    [-8,-3,4,2,1],
    [3,8,10,1,3],
    [-4,-1,1,7,-6]
]

R, C = len(mat), len(mat[0])
maxSum = float('-inf')

for left in range(C):
    temp = [0]*R
    for right in range(left, C):
        for i in range(R):
            temp[i] += mat[i][right]
        maxSum = max(maxSum, kadane(temp))

print(maxSum)

Output

29

JavaScript Implementation

function kadane(arr) {
    let maxSum = arr[0], curr = arr[0];
    for (let i = 1; i < arr.length; i++) {
        curr = Math.max(arr[i], curr + arr[i]);
        maxSum = Math.max(maxSum, curr);
    }
    return maxSum;
}

let mat = [
    [1,2,-1,-4,-20],
    [-8,-3,4,2,1],
    [3,8,10,1,3],
    [-4,-1,1,7,-6]
];

let R = mat.length, C = mat[0].length;
let maxSum = -Infinity;

for (let left = 0; left < C; left++) {
    let temp = new Array(R).fill(0);

    for (let right = left; right < C; right++) {
        for (let i = 0; i < R; i++)
            temp[i] += mat[i][right];

        maxSum = Math.max(maxSum, kadane(temp));
    }
}

console.log(maxSum);

Output

29

C# Implementation

using System;

class Program {

    static int Kadane(int[] arr) {
        int maxSum = arr[0], curr = arr[0];
        for(int i = 1; i < arr.Length; i++) {
            curr = Math.Max(arr[i], curr + arr[i]);
            maxSum = Math.Max(maxSum, curr);
        }
        return maxSum;
    }

    static void Main() {
        int[,] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };

        int R = 4, C = 5;
        int maxSum = int.MinValue;

        for(int left = 0; left < C; left++) {
            int[] temp = new int[R];

            for(int right = left; right < C; right++) {
                for(int i = 0; i < R; i++)
                    temp[i] += mat[i, right];

                maxSum = Math.Max(maxSum, Kadane(temp));
            }
        }

        Console.WriteLine(maxSum);
    }
}

Output

29

Summary

• Brute force checks all rectangles but is impractical
• Prefix sum improves calculation but still slow
• Kadane-based solution is optimal and interview-preferred
• Converts 2D problem into multiple 1D max subarray problems

Next Problem in the Series

Subarray Sum Equals K (Prefix Sum + Hashing)