Question 2

September 8, 2020

Code for Finding Maximum Sum Submatrix in a given matrix

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

12 comments on “Question 2”


  • Varsha Singh

    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)


  • Nageswar

    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()


  • 4PS20EC420

    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]]


  • sandeep

    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)


  • RAIHAN

    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))


  • Avirup

    #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;
    }


  • Gourav

    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)


  • Ranjith

    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);

    }

    }


  • SAYAN

    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();
    }

    }

    }

    }


  • Shreyas

    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);
    }


  • Hritik

    #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;
    }


    • preeti

      #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)