# Accepted Java Solution

• The idea of this solution is to convert the problem into "find the maximum sum of sub-array no larger than K".

The time complexity will be O(r^2clogc) where r is the number of rows and c is the number of columns. If r is much larger than c, the complexity can be O(c^2rlogr) by creating a row-sum array instead of column-sum array

``````
public class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int row = matrix.length;
int col = matrix[0].length;
int max = Integer.MIN_VALUE;
for (int i = 0; i < row; i ++) {
int[] colSum = new int[col];
for (int j = i; j < row; j ++) {
for (int c = 0; c < col; c ++) {
colSum[c] += matrix[j][c];
}
max = Math.max(max, findMax(colSum, k));
}
}
return max;
}

private int findMax(int[] nums, int k) {
int max = Integer.MIN_VALUE;
int sum = 0;
TreeSet<Integer> s = new TreeSet();

for(int i = 0;i < nums.length; i ++){
int t = sum + nums[i];
sum = t;
Integer gap = s.ceiling(sum - k);
if(gap != null) max = Math.max(max, sum - gap);