Data Structure & Algorithms
Arrays Two Dimensional
Maximum Submatrix Sum

# Maximum Submatrix Sum

## Problem Description

Given a row-wise and column-wise sorted matrix A of size N * M. Return the maximum non-empty submatrix sum of this matrix.

### Problem Constraints

``````1 <= N, M <= 1000
-109 <= A[i][j] <= 10^9``````

### Input Format

``The first argument is a 2D integer array A.``

### Output Format

``Return a single integer that is the maximum non-empty submatrix sum of this matrix.``

### Example Input

``````Input 1:
-5 -4 -3
A = -1  2  3
2  2  4

Input 2:
1 2 3
A = 4 5 6
7 8 9
``````

### Example Output

``````Output 1:
12

Output 2:
45
``````

### Example Explanation

``````Explanation 1:
The submatrix with max sum is
-1 2 3
2 2 4
Sum is 12.

Explanation 2:
The largest submatrix with max sum is
1 2 3
4 5 6
7 8 9
The sum is 45.``````

### Output

Java
``````public class MaximumSubmatrixSum {
public int maximumSubmatrixSum(int[][] A) {
int rows = A.length;
int cols = A[0].length;
int maxSum = Integer.MIN_VALUE;

for (int left = 0; left < cols; left++) {
int[] temp = new int[rows];
for (int right = left; right < cols; right++) {
for (int i = 0; i < rows; i++) {
temp[i] += A[i][right];
}

int currSum = 0, maxCurr = Integer.MIN_VALUE;
for (int val : temp) {
currSum = Math.max(val, currSum + val);
maxCurr = Math.max(maxCurr, currSum);
}

maxSum = Math.max(maxSum, maxCurr);
}
}

return maxSum;
}
}``````
Python
``````def maximumSubmatrixSum(A):
rows, cols = len(A), len(A[0])
max_sum = float('-inf')

for left in range(cols):
temp = [0] * rows
for right in range(left, cols):
for i in range(rows):
temp[i] += A[i][right]

curr_sum, max_curr = 0, float('-inf')
for val in temp:
curr_sum = max(val, curr_sum + val)
max_curr = max(max_curr, curr_sum)

max_sum = max(max_sum, max_curr)

return max_sum``````
JavaScript
``````function maximumSubmatrixSum(A) {
const rows = A.length;
const cols = A[0].length;
let maxSum = Number.NEGATIVE_INFINITY;

for (let left = 0; left < cols; left++) {
const temp = new Array(rows).fill(0);
for (let right = left; right < cols; right++) {
for (let i = 0; i < rows; i++) {
temp[i] += A[i][right];
}

let currSum = 0;
let maxCurr = Number.NEGATIVE_INFINITY;
for (const val of temp) {
currSum = Math.max(val, currSum + val);
maxCurr = Math.max(maxCurr, currSum);
}

maxSum = Math.max(maxSum, maxCurr);
}
}

return maxSum;
}``````