Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Question 2

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

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

One comment on “Question 2”


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