## Flipkart Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Phone Interview

convolve the original matrix with the matrix of ones (Kernel) and fing the max value of the 2D matrix. which will return the center position of the submatrix with the largest sum.

Size of the kernal will decide the size of the sunMatrix.

in matlab it can be done like this

```
orignal2DMatrix;
subMatKernal = ones(sizeOfSubMatrix,sizeOfSubMatrix);
result = conv2(orignal2DMatrix,subMatKernal );
matrixIndex= find(max(result));
```

Logic:

Step 1:

Row wise operation:

Replace the matrix data with the sum of element in row upto current column number.

Replace A[x,y] = A[x,0]+A[x,1]+A[x,2]+A[x,3]+......+A[x,y]

If A =

[1 2 3]

[4 5 6]

[7 8 9]

then after first step:

A=

[1 3 6]

[4 9 15]

[7 15 24]

Step 2:

Column wise operation:

Replace the matrix data with the sum of element in column upto current row number.

Replace A[x,y] = A[0,y]+A[1,y]+A[2,y]+A[3,y]+......+A[x,y]

Now A =

A=

[1 3 6]

[5 12 21]

[12 27 45]

Step 3:

Now find the max diff b/w to A[x,y]-A[x',y'] elements in the result matrix where

X>=X' and

Y>=Y'

Check "Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)" on geeks for geeks site.

- 42 May 21, 2014