# Given a 2D matrix, find the submatrix which sum of all elements is max

• public int subMaxMatrix(int[][] matrix) {

``````	int[][] total = matrix;
for (int i = 1; i < matrix[0].length; i++) {
for (int j = 0; j < matrix.length; j++) {
total[i][j] += total[i-1][j];
}
}

int maximum = Integer.MIN_VALUE;
for (int i = 0; i < matrix.length; i++) {
for (int j = i; j < matrix.length; j++) {
int[] result = new int[matrix[0].length];
for (int f = 0; f < matrix[0].length; f++) {
if (i == 0) {
result[f] = total[j][f];
} else {
result[f] = total[j][f] - total[i - 1][f];
}
}
int maximal = maxSubsequence(result);

if (maximal > maximum) {
maximum = maximal;
}
}
}
return maximum;
``````

}

• ``````b[][]=0
for j 0->n-1:
int sum=0;
for i 0->m-1;
b[i+1][j]+=b[i][j];
int maxsum=INT_MIN;
for i 0->m-1:
int sum=0;
for j i->m-1:
dp = 0
for k in 0->n-1:
sum+=b[j+1][k]-b[i][k]
dp=max(dp+sum, sum);
maxsum=max(maxsum, dp);
return maxsum;``````

• is there's a O(N^2) solution?

• Here is my runnable code:

This is the result class to store the desired sub matrix:

``````public class result {
public int row, col, col_size, row_size;
}
``````

Here is the rest of the code:

``````public class questions {

public static void main(String[] args) {

int [][] matrix = new int[][]{
{2, 2, 8},
{1, 3, -9}
};

result res = new result();
System.out.println("max sum = " + subMatrixSum(matrix, res));
System.out.print("row = " + res.row + " col = " + res.col + " row size =" + res.row_size + " col size = " + res.col_size);

}

public static int subMatrixSum(int[][] matrix, result res) {
int maxSum = -Integer.MAX_VALUE;

for (int i = 1; i <= matrix.length; i++)
for (int j = 1; j <= matrix[0].length; j++)
for (int iIndex = 0; iIndex < matrix.length - i + 1; iIndex++)
for (int jIndex = 0; jIndex < matrix[0].length - j + 1; jIndex++) {
int sum = 0;

for (int k_i = iIndex; k_i < iIndex + i; k_i++)
for (int k_j = jIndex; k_j < jIndex + j; k_j++)
sum += matrix[k_i][k_j];

if (maxSum < sum) {
maxSum = sum;
res.row = iIndex;
res.col = jIndex;
res.row_size = i;
res.col_size = j;
}
}
return maxSum;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.