Decide to post because I was actually asked this question during my interview!

There is a simple version of O(n^4).

The idea is to calculate every rectangle [[r1,c1], [r2,c2]], and simply pick the max area <= k.

An improved version takes O(n^3logn). It borrows the idea to find max subarray with sum <= k in 1D array, and apply here: we find all rectangles bounded between r1 & r2, with columns from 0 to end. Pick a pair from tree.

I remember the interviewer said there could be an even better solution, but I haven't figured that out...

Solution I, O(n^4):

```
public int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int rows = matrix.length, cols = matrix[0].length;
int[][] areas = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int area = matrix[r][c];
if (r-1 >= 0)
area += areas[r-1][c];
if (c-1 >= 0)
area += areas[r][c-1];
if (r-1 >= 0 && c-1 >= 0)
area -= areas[r-1][c-1];
areas[r][c] = area;
}
}
int max = Integer.MIN_VALUE;
for (int r1 = 0; r1 < rows; r1++) {
for (int c1 = 0; c1 < cols; c1++) {
for (int r2 = r1; r2 < rows; r2++) {
for (int c2 = c1; c2 < cols; c2++) {
int area = areas[r2][c2];
if (r1-1 >= 0)
area -= areas[r1-1][c2];
if (c1-1 >= 0)
area -= areas[r2][c1-1];
if (r1-1 >= 0 && c1 -1 >= 0)
area += areas[r1-1][c1-1];
if (area <= k)
max = Math.max(max, area);
}
}
}
}
return max;
}
```

Solution II (O(n^3logn)

```
public int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int rows = matrix.length, cols = matrix[0].length;
int[][] areas = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int area = matrix[r][c];
if (r-1 >= 0)
area += areas[r-1][c];
if (c-1 >= 0)
area += areas[r][c-1];
if (r-1 >= 0 && c-1 >= 0)
area -= areas[r-1][c-1];
areas[r][c] = area;
}
}
int max = Integer.MIN_VALUE;
for (int r1 = 0; r1 < rows; r1++) {
for (int r2 = r1; r2 < rows; r2++) {
TreeSet<Integer> tree = new TreeSet<>();
tree.add(0); // padding
for (int c = 0; c < cols; c++) {
int area = areas[r2][c];
if (r1-1 >= 0)
area -= areas[r1-1][c];
Integer ceiling = tree.ceiling(area - k);
if (ceiling != null)
max = Math.max(max, area - ceiling);
tree.add(area);
}
}
}
return max;
}
```