Categories

# Get maximum sum rectangle sub matrix in a 2D matrix

This problem can be solved using Kadane’s Algorithm.
We start by taking an empty array of zeros of size of the number of rows of input matrix.
We move from left to right columns and calculate max for every column and update up, down, left, right accordingly.
Input matrix mxn
Time = O(m*n*n)
Space = O(m)

```package algos;

import java.util.HashMap;

class solution {

public solution() {
}

public HashMap getMaxSum(int[] arr) {
int max = arr[0], start = 0, end = 0, mstart = 0, mend = 0, currmax = arr[0];
for (int i = 1; i < arr.length; i++) {

if (arr[i] > arr[i] + currmax) {
currmax = arr[i];
start = i;
end = i;
} else {
currmax = currmax + arr[i];
end = i;
}

if (currmax > max) {
max = currmax;
mstart = start;
mend = end;
}
}
HashMap result = new HashMap();
result.put("up", mstart);
result.put("down", mend);
result.put("max", max);
return result;
}

public HashMap getMaxSubArray(int[][] matrix) {
int max = matrix[0][0], left = 0, right = 0, up = 0, down = 0;
int[] rowArray = new int[matrix.length];
for (int cl = 0; cl < matrix[0].length; cl++) {
for (int i = 0; i < matrix.length; i++) {
rowArray[i] = 0;
}
for (int cr = cl; cr < matrix[0].length; cr++) {
for (int row = 0; row < matrix.length; row++) {
rowArray[row] += matrix[row][cr];
}
HashMap currentSet = getMaxSum(rowArray);
if (currentSet.get("max") > max) {
max = currentSet.get("max");
up = currentSet.get("up");
down = currentSet.get("down");
left = cl;
right = cr;
}
}
}

HashMap result = new HashMap();
result.put("up", up);
result.put("down", down);
result.put("left", left);
result.put("right", right);
result.put("max", max);
return result;
}

}

`max:6 up:1 down:1 left:0 right:2`