# Accepted Java simple solution (a little bit DP, but naive)

• ``````public class Solution {

int m=0;
int n=0;
int[][] sums2;
int[][] matrix;

public int maxSumSubmatrix(int[][] matrix, int k) {
this.matrix = matrix;

if(matrix==null) return 0;
m = matrix.length;
if(m==0) return 0;
n = matrix[0].length;
if(n==0) return 0;

/* sum2[i][j] = matrix[0][j] +...+ matrix[i][j],
* sum2 represents sum of a vertical area whose width is 1.
*/
sums2 = new int[n][m];

for(int j=0;j<n;j++) {
for(int i=0;i<m;i++) {
sums2[j][i] = (i==0 ? 0 : sums2[j][i-1]) + matrix[i][j];
}
}

int res = Integer.MIN_VALUE;

for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
for(int height=1;height<=m && i+height<=m;height++) {
int[] dp = new int[n+1];
for(int width=1;width<=n && j+width<=n;width++) {
dp[width] = dp[width-1] + getCol(i, j+width-1, height);
if(dp[width] == k) return k;
if(dp[width] < k && dp[width]>res) {
res = dp[width];
}
}
}
}
}
return res;
}

public int getCol(int i, int j, int height) {
if(height==1) {
return matrix[i][j];
} else {
if(i==0) {
return sums2[j][i+height-1];
} else {
return sums2[j][i+height-1] - sums2[j][i-1];
}
}
}
}
``````

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