找到边界元素总和最高的方形子矩阵

Question

考虑一个宽度和高度可变的 0 到 9 数字的二维矩阵。找到边界元素总和最高的方形子矩阵。

输入：

矩阵输入宽度和高度：6 8

数字从 0 到 9 的输入矩阵：

2

0 6 1 2 51 0 5 0 1 33 0 1 2 4 10 1 3 1 1 94 1 0 8 5 20 1 0 1 2 36 5 3 1 0 20 0 1 6 0 4方形子矩阵的输入最大宽度(方形子矩阵的高度和宽度相同(：3

输出：

由于突出显示的子矩阵的总和最大(边界元素的计算和仅为 2,4,1,9,2,5,8,1(，

2

0 6 1 2 51 0 5 0 1 33 0 1 2 4 10 1 3 1 1 94 1 0 8 5 20 1 0 1 2 36 5 3 1 0 20 0 1 6 0 4输出应为：

2 4 1
1 1 9
8 5 2

请用伪代码解释这一点。

Answer 1

#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 isn";
printMaxSumSub(mat, k);
    return 0;
}

//Output
the  sum  of 3 x 3 matrix is                                                                                                     
2 4 1                                                                                                                            
1 1 9                                                                                                                            
8 5 2