# I am surprised it beats 100%

• Similar to iaming's solution which uses merge sort
Calculate max rectangle sum before we merge

public class Solution {
private int res;

``````public int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
res = Integer.MIN_VALUE;
long[] sum = new long[m];
long[] helper = new long[m];
for (int j = 0; j < n; j++) {
long[] sumRow = new long[m];
for (int p = j; p < n; p++) {
for (int i = 0; i < m; i++) {
sumRow[i] += matrix[i][p];
sum[i] = (i == 0 ? 0 : sum[i - 1]) + sumRow[i];
}

//for (long i : sum) System.out.print(i + " ");
//System.out.println();
sortAndRecord(sum, 0, m - 1, helper, k);
if (res == k) return k;
}
}
return res;
}

private void sortAndRecord(long[] sum, int left, int right, long[] helper, int k) {
if (left == right) {
if (sum[left] <= k) res = Math.max(res, (int)sum[left]);
return;
}

int mid = left + (right - left) / 2;
sortAndRecord(sum, left, mid, helper, k);
sortAndRecord(sum, mid + 1, right, helper, k);

merge(sum, helper, left, mid, right, k);
}

private void merge(long[] sum, long[] helper, int left, int mid, int right, int k) {
for (int i = left; i <= right; i++) {
helper[i] = sum[i];
}

int leftI = left, rightI = mid + 1;
for (int i = rightI; leftI <= mid && i <= right; i++) {
if (helper[i] - helper[leftI] <= k) {
res = Math.max(res, (int)(helper[i] - helper[leftI]));
}else {
leftI++;
i--;
}
}
leftI = left;
while (leftI <= mid && rightI <= right) {
if (helper[leftI] < helper[rightI]) sum[left++] = helper[leftI++];
else sum[left++] = helper[rightI++];
}

while (leftI <= mid) {
sum[left++] = helper[leftI++];
}
}
``````

}

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