Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
0Question 2
Find Maximum Sum Submatrix in a given matrix
Given a M x N matrix, calculate maximum sum submatrix of size k x k in a given M x N matrix in O(M*N) time. Here, 0 < k < M, N.
For example, consider below 5 x 5 matrix
[ 3 -4 6 -5 1 ]
[ 1 -2 8 -4 -2 ]
[ 3 -8 9 3 1 ]
[ -7 3 4 2 7 ]
[ -3 7 -5 7 -6 ]
If k = 2, maximum sum k x k sub-matrix is
[ 9 3 ]
[ 4 2 ]
If k = 3, maximum sum k x k sub-matrix is
[ 8 -4 -2 ]
[ 9 3 1 ]
[ 4 2 7 ]
How to solve this question:
The idea is to pre-process the matrix. We take an auxiliary matrix sum[][] where sum[i][j] will store the sum of the elements in matrix from (0, 0) to (i, j). We can easily calculate the value of sum[i][j] in constant time using below relation –
sum[i][j] = sum[i][j – 1] + sum[i – 1][j] + mat[i][j] – sum[i – 1][j – 1];
Now to find maximum sum k x k sub-matrix, we consider every sub-matrix of size k x k and calculate their sum in constant time by directly using below relation –
submatrixSum = sum[i][j] – sum[i – k][j] – sum[i][j – k] + sum[i – k][j – k];
Here, (i, j) is bottom right corner coordinates of k x k sub-matrix. Finally, we print the sub-matrix that has maximum sum.
Code for finding the maximum sum sub-matrix in a given matrix
#include <bits/stdc++.h> using namespace std; #define N 5 void printMaxSumSub (int mat[][N], int k) { // k must be smaller than or equal to n if (k > N) return; // 1: PREPROCESSING // To store sums of all strips of size k x 1 int stripSum[N][N]; // Go column by column for (int j = 0; j < N; j++) { // Calculate sum of first k x 1 rectangle // in this column int sum = 0; for (int i = 0; i < k; i++) sum += mat[i][j]; stripSum[0][j] = sum; // Calculate sum of remaining rectangles for (int i = 1; i < N - k + 1; i++) { sum += (mat[i + k - 1][j] - mat[i - 1][j]); stripSum[i][j] = sum; } } // max_sum stores maximum sum and its // position in matrix int max_sum = INT_MIN, *pos = NULL; // 2: CALCULATE SUM of Sub-Squares using stripSum[][] for (int i = 0; i < N - k + 1; i++) { // Calculate and print sum of first subsquare // in this row int sum = 0; for (int j = 0; j < k; j++) sum += stripSum[i][j]; // Update max_sum and position of result if (sum > max_sum) { max_sum = sum; pos = &(mat[i][0]); } // Calculate sum of remaining squares in // current row by removing the leftmost // strip of previous sub-square and adding // a new strip for (int j = 1; j < N - k + 1; j++) { sum += (stripSum[i][j + k - 1] - stripSum[i][j - 1]); // Update max_sum and position of result if (sum > max_sum) { max_sum = sum; pos = &(mat[i][j]); } } } // Print the result matrix for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) cout << *(pos + i * N + j) << " "; cout << endl; } } // Driver program to test above function int main () { int mat[N][N] = { {1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 8, 6, 7, 3}, {4, 4, 4, 4, 4}, {5, 5, 5, 5, 5}, }; int k = 3; cout << "Maximum sum 3 x 3 matrix is\n"; printMaxSumSub (mat, k); return 0; }
Login/Signup to comment
python code :
def maxsum_submartix(arr,k)
l=len(arr)
max=0
# new=[]
max_indexi=0
max_indexj=0
if lmax:
max=sum
max_index=i
max_index=j
#print(sum,end=” “)
#print(“/n”)
print(max_indexi,max_indexj)
for c in range(max_indexj,max_indexj+ k)
for r in range(max_indexj,max_indexj+k)
prit(arr[c][r],end=””)
print(“\ n”) if __name___==’__main__’:
arr=[[3,-4,6,-5,1][1,-2,8,-4,-2][3,-8,9,3],[-7,3,4,2,7],[-3,7,-5,7,-6]]
k = int(input())
maxsum submartix(arr,k)
m, n = map(int, input().split())
a = []
o, p = 0, 0
mm = -1
for i in range(m):
a.append(list(map(int, input().split())))
k=int(input())
for i in range(m – k + 1):
x = a[i:i + k]
for j in range(i, n – k + 1):
s = 0
for l in range(k):
s += sum(x[l][j:j + k])
if s > mm:
mm = s
o = i
p = j
x = a[o:o + k]
for i in x:
for j in i[p:p + k]:
print(j, end=” “)
print()
import numpy as np
def hi(a,k):
a1=[]
l1=[]
l=len(a)
if l<k:
return 0
for i in range(l-k+1):
for j in range(l-k+1):
s=0
for p in range(i,i+k):
for q in range(j,j+k):
s+=a[p][q]
l1.append(a[p][q])
a1.append(s)
return a1,l1
n=int(input("size:"))
k=int(input("sub:"))
N=k*k
l=list(map(int,input("array elements are:\n").strip().split(',')))[:n*n]
a=np.array(l)
a=a.reshape(n,n)
l1,a1=hi(a,k)
group=[a1[n:n+N]for n in range(0,len(a1),N)]
m=max(l1)
pos=l1.index(m)
final=group[pos]
final=np.array(final)
final=final.reshape(k,k)
print(final)
sample input and output:
size:5
sub:2
array elements are:
3,-4,6,-5,1,1,-2,8,-4,-2,3,-8,9,3,1,-7,3,4,2,7,-3,7,-5,7,-6
[[9 3]
[4 2]]
Python code:
def maxsum_submatrix(arr,k):
l = len(arr)
max =0
#new =[]
max_indexi=0
max_indexj =0
if lmax:
max = sum
max_indexi =i
max_indexj =j
#print(sum,end =” “)
#print(“\n”)
print(max,max_indexi,max_indexj)
for c in range(max_indexi,max_indexi+k):
for r in range(max_indexj,max_indexj+k):
print(arr[c][r],end=” “)
print(“\n”)
if __name__ == ‘__main__’:
arr = [[3,-4,6,-5,1],[1,-2,8,-4,-2],[3,-8,9,3,1],[-7,3,4,2,7],[-3,7,-5,7,-6]]
k = int(input())
maxsum_submatrix(arr,k)
in Python
#maximun sum of k size sub matrix
l = []
#k = int(input())
k = 2
s = []
#for _ in range(int(input())):
# l.append(list(map(int,input().split()))) or
l1 = [3,-4,6,-5,1]
l2 = [1,-2,8,-4,-2]
l3 = [3,-8,9,3,1]
l4 = [-7,3,4,2,7]
l5 = [-3,7,-5,7,-6]
l.extend([l1,l2,l3,l4,l5])
for i in l:
print(*i)
lo1,lo2=0,0
up1,up2=k,k
def myfun(lo1,up1,lo2,up2):
sum=0
for i in range(len(l)-k+1):
for i1 in range(lo1,up1):
for j1 in range(lo2,up2):
sum+=l[i1][j1]
lo2+=1
up2+=1
s.append(sum)
sum=0
for i in range(len(l)-k+1):
myfun(lo1,up1,lo2,up2)
lo2=0
up2=k
lo1+=1
up1+=1
print(max(s))
#include
using namespace std;
int main()
{
int *arr,*auxArray;
int r,c,i,j,k,p;
int subMatrixSum,maxSum=INT_MIN;
int i_min,j_min,k_max;
cin>>r>>c;
arr=new int[r*c];
for(i=0;i<r;i++)
{
for(j=0;j>arr[i*c+j];
}
}
auxArray=new int[r*c];
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if(i==0||j==0)
{
auxArray[i*c+j]=arr[i*c+j];
}
else
{
auxArray[i*c+j]=auxArray[(i-1)*c+j]+auxArray[i*c+j-1]+arr[i*c+j]-auxArray[(i-1)*c+j-1];
}
}
}
p=(r<c)?r:c;
for(k=1;k<=p;k++)
{
for(i=k;i<r;i++)
{
for(j=k;j<c;j++)
{
subMatrixSum=auxArray[i*c+j]-auxArray[(i-k)*c+j]-auxArray[i*c+j-k]+auxArray[(i-k)*c+j-k];
if(maxSum<subMatrixSum)
{
maxSum=subMatrixSum;
i_min=i-k+1;
j_min=j-k+1;
k_max=k;
}
}
}
}
cout<<"\nMaximum Sum SubArray is:"<<endl;
for(i=i_min;i<i_min+k_max;i++)
{
for(j=j_min;j<j_min+k_max;j++)
{
cout<<arr[i*c+j]<<" ";
}
cout<<"\n";
}
return 0;
}
s1=[[3,-4,6,-5,1],[1,-2,8,-4,-2],[3,-8,9,3,1],[-7,3,4,2,7],[-3,7,-5,7,-6]]
k=3
dp=[[0 for i in range (len(s1[0])+1)] for i in range (len(s1)+1)]
for i in range (1,len(s1)+1):
for j in range (1,len(s1[0])+1):
dp[i][j]=s1[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
#by-Gourav Raghuwanshi
”’
dp=[[0, 0, 0, 0, 0, 0], dp= [-1,12] by dp—-> 16-5-7+3=7 s1=[-2,8]
[0, 3, -1, 5, 0, 1], [-7,16] by s1—-> -2+8-2+9=7 [-8,9]
[0, 4, -2, 12, 3, 2],
[0, 7, -7, 16, 10, 10],
[0, 0, -11, 16, 12, 19],
[0, -3, -7, 15, 18, 19]]
”’
maxsum=0
curr=0
for i in range (1,len(s1)+1):
for j in range (1,len(s1[0])+1):
if(i-1+k<=len(s1) and j-1+kmaxsum):
maxsum=curr
print(maxsum)
#print(dp)
import java.util.Scanner;
public class maxSumsubmat {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int arr[][] =new int[4][5];
for(int i=0;i<arr.length;i++) {
for(int j=0;j<arr[0].length;j++) {
arr[i][j]=(int)(Math.random()*10);
}
}
int count=1;
int n=arr.length;
int k=3;
int max=0;
for(int i=0;i+k<=n;i++) {
for(int j=0;j+k<=arr[0].length;j++){
int sum=0;
for(int m1=i;m1<i+k;m1++)
for(int m=j;mmax) {
max=sum;
}
}
}
// for(int i=0;i<arr.length;i++) {
// for(int j=0;j<arr[0].length;j++) {
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
System.out.println(max);
}
}
Solution in JAVA:
import java.util.Scanner;
public class MaxSumSubmatrixOfParentMatrix {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int m = sc.nextInt(), n = sc.nextInt(), k, sum = 0, tempSum = 0, i_start, i_end, j_start, j_end, pos_i = 0, pos_j = 0, p, q;
int arr[][] = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j m || k > n) {
System.out.println(“INVALID INPUT: value of k should be less than m and n”);
} else {
i_start = 0; // initializing the values of i and j
j_start = 0;
i_end = k – 1;
j_end = k – 1;
for(int i = 0; i < k; i++) {
for(int j = 0; j < k; j++) {
sum = sum + arr[i][j]; // initial sum of sub array of size k x k
}
}
// System.out.println("initial sum: " + sum);
while(pos_i + k <= m) {
while(pos_j + k <= n) {
for(int i = pos_i; i < pos_i + k; i++) {
for(int j = pos_j; j sum) {
sum = tempSum;
i_start = pos_i;
j_start = pos_j;
i_end = pos_i + k;
j_end = pos_j + k;
}
tempSum = 0;
pos_j++;
}
pos_i++;
pos_j = 0;
}
System.out.println(“sum max sub array of ” + k + ” x ” + k + ” size is: ” + sum);
for(int i = i_start; i < i_end; i++) {
for(int j = j_start; j < j_end; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
}
what if, we do this:
#include
#define R 5
#define C 5
#define ms 3
int sumof (int a, int b, int ms1,int M[R][C])
{
int m=0;
for (int i=a;i>a-ms1;i–)
for(int j=b;j>b-ms1;j–)
m+=M[i][j];
return m;
}
void printMaxSubSquare (int M[R][C])
{
int i, j;
int S[R][C];
int max_of_s, max_i, max_j;
/* Set first ms-1 columns of S[][]*/
for (j=0; j<ms-1; j++)
for (i = 0; i < R; i++)
S[i][j] = M[i][j];
/* Set first ms -1 rows of S[][]*/
for (i=0;i<ms-1;i++)
for (j = 0; j < C; j++)
S[i][j] = M[i][j];
max_of_s = S[0][0];
max_i = 0;
max_j = 0;
for (i = ms-1; i < R; i++)
{
for (j = ms-1; j < C; j++)
{
S[i][j] = sumof(i,j,ms,M);
if (max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}
printf("%d,%d,%d\n",max_i,max_j,max_of_s);
printf ("Maximum size sub-matrix of size %dx%d is: \n",ms,ms);
for (i = max_i-(ms-1); i <= max_i; i++)
{
for (j = max_j-(ms-1); j <= max_j; j++)
{
printf ("%d ", M[i][j]);
}
printf ("\n");
}
}
int main ()
{
int M[R][C] = {
{ 3, -4, 6, -5, 1 },
{ 1, -2, 8, -4, -2 },
{ 3, -8, 9, 3, 1 },
{ -7, 3, 4, 2, 7 },
{ -3, 7, -5, 7, -6 }
};
printMaxSubSquare (M);
}
#include
using namespace std;
#define row 4
#define col 5
int kedans(int arr[] ,int *start,int *finish,int n){
int max_so_far = arr[0] , max_end_here=0;
int s=0,i;
for(i=0;i<n;i++){
max_end_here+=arr[i];
if(max_so_far<max_end_here){
max_so_far=max_end_here;
*start = s;
*finish=i;
}
if(max_end_here<0){
max_end_here=0;
s=i+1;
}
}
return max_so_far;
}
void findmaxsumarray(int arr[][col]){
int maxsum=0,maxleft=0,maxright=0,maxup=0,maxdown=0;
int left,right,temp[row],start,finish,currentsum=0,i;
for(left=0;left<col;left++){
memset(temp, 0, sizeof(temp));
for(right=left;right<col;right++){
for(i=0;imaxsum){
maxsum=currentsum;
maxleft=left;
maxright = right;
maxup=start;
maxdown=finish;
}
}
}
cout<<"top left : "<<maxup<<" , "<<maxleft<<endl;
cout<<"bottom right : "<<maxdown<<" , "<<maxright<<endl;
cout<<maxsum;
}
int main(){
int arr[row][col]= {{1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 10, 1, 3},
{-4, -1, 1, 7, -6}};
findmaxsumarray(arr);
return 0;
}
#Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
def print_max_sub_matrix(grid):
r=len(grid)
c=len(grid[0])
cache=[[0 for k in range(c) ] for l in range(r)]
for i in range(0,r):
for j in range(0,c):
if grid[i][j]==1:
if i==0 or j==0:
cache[i][j]=min(grid[i][j],1)
else:
cache[i][j]=min(cache[i][j-1],cache[i-1][j],cache[i-1][j-1])+1
else:
cache[i][j]=0
max_cache=cache[0][0]
max_i=0
max_j=0
for i in range(r):
for j in range(c):
if max_cache<=cache[i][j]:
max_cache=cache[i][j]
max_i=i
max_j=j
for i in range(max_i,max_i-max_cache,-1):
for j in range(max_j,max_j-max_cache,-1):
print(grid[i][j],end=" ")
print()
grid = [
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 0],
[1, 1, 1, 1, 0],
[0, 1, 1, 1, 0],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 0]
]
print("Maximum sub-matrix:")
print_max_sub_matrix(grid)