Maximum Sum Square SubMatrix Solution InterviewBit

 

Maximum Sum Square SubMatrix

Problem Description

Given a 2D integer matrix A of size N x N find a B x B submatrix where B<= N and B>= 1, such that sum of all the elements in submatrix is maximum.

Problem Constraints

1 <= N <= 103.

1 <= B <= N

-102 <= A[i][j] <= 102.

Input Format

First arguement is an 2D integer matrix A.

Second argument is an integer B.

Output Format

Return a single integer denoting the maximum sum of submatrix of size B x B.

Example Input

Input 1:

 A = [
        [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]
     ]
 B = 3

Input 2:

 A = [
        [2, 2]
        [2, 2]
    ]
 B = 2

Example Output

Output 1:

 48

Output 2:

 8

Example Explanation

Explanation 1:

    Maximum sum 3 x 3 matrix is
    8 6 7
    4 4 4
    5 5 5
    Sum = 48

Explanation 2:

 Maximum sum 2 x 2 matrix is
  2 2
  2 2
  Sum = 8

Solution - Learn about Prefix sum in 2D Matrix

int Solution::solve(vector<vector<int> > &v, int k) {
    int ans=INT_MIN,n=v.size();
    vector<vector<int>>sum(v.size(),vector<int>(v.size(),0));
    sum[0][0]=v[0][0];
    for(int j=1; j<n; j++)sum[0][j]=sum[0][j-1]+v[0][j];
    for(int i=1; i<n; i++)sum[i][0]=sum[i-1][0]+v[i][0];
    
    for(int i=1; i<n; i++){
        for(int j=1; j<n; j++)
        sum[i][j]=v[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    }
    for (int i = k - 1; i < n; i++)
    {
        for (int j = k - 1; j < n; j++)
        {
 
            int total = sum[i][j];
            if (i - k >= 0) {
                total = total - sum[i - k][j];
            }
 
            if (j - k >= 0) {
                total = total - sum[i][j - k];
            }
 
            if (i - k >= 0 && j - k >= 0) {
                total = total + sum[i - k][j - k];
            }
 
            ans=max(ans,total);
        }
    }
    return ans;
    
    
}

	int Solution::solve(vector<vector<int> > &v, int k) {
	int ans=INT_MIN,n=v.size();
	vector<vector<int>>sum(v.size(),vector<int>(v.size(),0));
	sum[0][0]=v[0][0];
	for(int j=1; j<n; j++)sum[0][j]=sum[0][j-1]+v[0][j];
	for(int i=1; i<n; i++)sum[i][0]=sum[i-1][0]+v[i][0];
	for(int i=1; i<n; i++){
	for(int j=1; j<n; j++)
	sum[i][j]=v[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	}
	for (int i = k - 1; i < n; i++)
	{
	for (int j = k - 1; j < n; j++)
	{
	int total = sum[i][j];
	if (i - k >= 0) {
	total = total - sum[i - k][j];
	}
	if (j - k >= 0) {
	total = total - sum[i][j - k];
	}
	if (i - k >= 0 && j - k >= 0) {
	total = total + sum[i - k][j - k];
	}
	ans=max(ans,total);
	}
	}
	return ans;
	}

Made with ❤ by Raunit Verma Rate Us 5⭐ Here