# Java DP O(m*m*n*n) solution, 262 ms

• Use a sum array to store the accumulated sum value of each row. And then calculate all the possible values ( check each sum[i1...i2][j1....j2])

``````public class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length;
if(m < 1)return 0;
int n = matrix[0].length;
int[][] sum = new int[m+1][n+1];
for(int j = 1; j <= n; j++){
for(int i = 1; i <= m; i++){
sum[i][j] = sum[i][j-1] + matrix[i-1][j-1];
}
}
int res = Integer.MIN_VALUE;
for(int j = 0; j < n; j++){
for(int j2 = j+1; j2 <= n; j2++){
int[] row = new int[m+1];
int[] sumRow = new int[m+1];
for(int i = 1; i <= m; i++){
row[i] = sum[i][j2] - sum[i][j];
sumRow[i] = sumRow[i-1]+row[i];
}
for(int i = 0; i < m; i++){
for(int i2 = i+1; i2 <= m; i2++){
int tmp = (sumRow[i2] - sumRow[i]);
if(tmp <= k && tmp > res){
res = tmp;
if(tmp == k)return k;
}
}
}
}
}
return res;
}
}
``````

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