O(row^3*col^2) solution. maxSubArray O(row^2) should be able to optimize.

• The solution came out immediately after I saw this video. https://www.youtube.com/watch?v=yCQN096CwWM

``````    public int maxSumSubmatrix(int[][] matrix, int k) {
int row = matrix.length;
int col = matrix[0].length;
int[] arr = new int[row];

//the total complexity would be O(row^3*col^2), space is O(row)
for (int i = 0; i < col; i++) {
arr = new int[row];
for (int j = i; j < col; j++) {
for (int l = 0; l < row; l++) {
arr[l] += matrix[l][j];
}
int temp = findMaxSubArray(arr, k);
if (temp == k) {
return k;
}
maxValue = Math.max(maxValue, temp);
}
}
return maxValue;
}

public int findMaxSubArray(int[] arr, int k) {
//this function should be able to optimize. I just used brute force. O(row^2);
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
int cumSum = 0;
for(int j = i; j < arr.length; j++) {
cumSum += arr[j];
if (cumSum <= k) {
maxSum = Math.max(cumSum, maxSum);
}
}
}
return maxSum;
}`````````

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