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
34
| class Solution {
public int[] getMaxMatrix(int[][] matrix) {
int[] res = new int[4];
int maxSum = Integer.MIN_VALUE;
for (int startRowIndex = 0; startRowIndex < matrix.length; startRowIndex++) {
int[] prefixSumsOnCol = new int[matrix[0].length];
for (int endRowIndex = startRowIndex; endRowIndex < matrix.length; endRowIndex++) {
int matrixSum = 0;
int startColIndex = 0;
for (int endColIndex = startColIndex; endColIndex < matrix[0].length; endColIndex++) {
prefixSumsOnCol[endColIndex] += matrix[endRowIndex][endColIndex];
if (matrixSum < 0) {
matrixSum = prefixSumsOnCol[endColIndex];
startColIndex = endColIndex;
} else {
matrixSum += prefixSumsOnCol[endColIndex];
}
if (matrixSum > maxSum) {
maxSum = matrixSum;
res[0] = startRowIndex;
res[1] = startColIndex;
res[2] = endRowIndex;
res[3] = endColIndex;
}
}
}
}
return res;
}
}
|