Consider a 2D matrix of numbers from 0 to 9 with variable width and height. Find the square submatrix with the highest sum of boundary elements.
Answers
Input :
Input width and height of matrix: 6 8
Input Matrix with numbers from 0 to 9:
2 0 6 1 2 5
1 0 5 0 1 3
3 0 1 2 4 1
0 1 3 1 1 9
4 1 0 8 5 2
0 1 0 1 2 3
6 5 3 1 0 2
0 0 1 6 0 4
Input maximum width of square submatrix (for square submatrix height and width are same) : 3
Output :
As sum of highlighted submatrix is maximum (calcute sum of boundary elements only 2,4,1,9,2,5,8,1),
2 0 6 1 2 5
1 0 5 0 1 3
3 0 1 2 4 1
0 1 3 1 1 9
4 1 0 8 5 2
0 1 0 1 2 3
6 5 3 1 0 2
0 0 1 6 0 4
Output should be :
2 4 1 1 1 9
8 5 2
#include <bits/stdc++.h>
using namespace std;
#define R 8
#define C 6
// matrix of size R x C
void printMaxSumSub(int mat[R][C], int k)
{
if (k > C) return;
int stripSum[R][C];
// Go column by column
for (int j=0; j<C; j++)
{
int sum = 0;
for (int i=0; i<k; i++)
sum += mat[i][j];
stripSum[0][j] = sum;
// sum of remaining rectangles
for (int i=1; i<R-k+1; i++)
{
sum += (mat[i+k-1][j] - mat[i-1][j]);
stripSum[i][j] = sum;
}
}
// max_sum stores maximum sum
int max_sum = INT_MIN, *pos = NULL;
for (int i=0; i<R-k+1; i++)
{
int sum = 0;
for (int j = 0; j<k; j++)
sum += stripSum[i][j];
if (sum > max_sum)
{
max_sum = sum;
pos = &(mat[i][0]);
}
for (int j=1; j<R-k+1; j++)
{
sum += (stripSum[i][j+k-1] - stripSum[i][j-1]);
if (sum > max_sum)
{
max_sum = sum;
pos = &(mat[i][j]);
}
}
}
for (int i=0; i<k; i++)
{
for (int j=0; j<k; j++)
cout << *(pos + i*C + j) << " ";
cout << endl;
}
}
// function
int main()
{
int mat[R][C] = {{2, 0 ,6 ,1 ,2, 5},
{1, 0, 5, 0 ,1, 3},
{3 ,0, 1 ,2 ,4 ,1},
{0 ,1, 3, 1, 1, 9},
{4 ,1, 0 ,8 ,5 ,2},
{0 ,1, 0, 1 ,2 ,3},
{6 ,5 ,3 ,1 ,0, 2},
{0 ,0, 1, 6, 0, 4}
};
int k = 3;
cout << "the sum of 3 x 3 matrix is\n";
printMaxSumSub(mat, k);
return 0;
}
//Output
the sum of 3 x 3 matrix is
2 4 1
1 1 9
8 5 2