1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int row = matrix.length;
int columns = matrix[0].length;
int[][] dp = new int[row+1][columns+1];
dp[1][1] = matrix[0][0];
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= columns; j++) {
int ans = 0;
for (int l = 1; l <= i; l++) {
ans += matrix[l-1][j-1];
}
dp[i][j] = dp[i][j-1] + ans;
}
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < row; i++) {
for (int j = 0; j < columns ; j++) {
for (int i2 = i + 1; i2 <= row; i2++) {
for (int j2 = j + 1; j2 <= columns; j2++) {
int val = dp[i2][j2] - dp[i][j2] - dp[i2][j] + dp[i][j];
if (val <= k) {
res = Math.max(res, val);
}
}
}
}
}
return res;
}
}
|
