在C ++中找到面积总和等于k的最大面积矩形子矩阵
假设我们有一个二维矩阵矩阵和一个值K，我们必须找到最长的矩形子矩阵，其总和与K相同。
所以，如果输入像
K=9
那么输出将是左上点(1,0)和下右点(3,2)。
为了解决这个问题，我们将遵循以下步骤-
最大：=100
定义一个函数sum_k()，它将使用一个数组arr，start，end，n，k，
定义一张映射
总和：=0，最大长度：=0
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
如果maximum_length<（i-map[sum-k]），则-
maximum_length：=i-map[sum-k]
开始：=map[sum-k]+1
结束：=我
map[sum]：=i
最大长度：=i+1
开始：=0
结束：=我
sum：=sum+arr[i]
如果和等于k，则-
如果总和不在映射中，则-
如果(sum-k)在映射中，则-
当maximum_length不为0时返回true
从主要方法中，执行以下操作-
row：=垫子的行数，col：=垫子的列数
定义大小为行的数组临时文件。
定义一个数组final_point={0,0,0,0}
maxArea：=-inf
对于initialleft：=0，当left<col时，更新（将left增加1），执行-
返回“未找到子矩阵”
对于初始化i：=0，当i<行，更新（将i增加1）时，执行-
sum：=sum_k（温度，上，下，行，k）
区域：=（下-上+1）*（右-左+1）
如果sum为非零且maxArea<area，则-
temp[i]：=temp[i]+mat[i，right]
final_point[0]：=向上，final_point[1]：=向下
final_point[2]：=左，final_point[3]：=右
maxArea：=面积
用0填充温度
对于初始化right：=left，当right<col时，更新（将right增加1），执行-
如果final_point是[0,0,0,0]并且mat[0,0]不是k，则
显示左上角的点（final_point[0]，final_point[2]）
显示右下角的点（final_point[1]，final_point[3]）
显示垫子元素。
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
bool sum_k(int arr[], int& start, int& end, int n, int k) {
unordered_map<int, int> map;
int sum = 0, maximum_length = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == k) {
maximum_length = i + 1;
start = 0;
end = i;
}
if (map.find(sum) == map.end())
map[sum] = i;
if (map.find(sum - k) != map.end()) {
if (maximum_length < (i - map[sum - k])) {
maximum_length = i - map[sum - k];
start = map[sum - k] + 1;
end = i;
}
}
}
return (maximum_length != 0);
}
void sum_zero(vector<vector<int>> &mat, int k) {
int row = mat.size();
int col = mat[0].size();
int temp[row], area;
bool sum;
int up, down;
vector<int> final_point = {0,0,0,0};
int maxArea = INT_MIN;
for (int left = 0; left < col; left++) {
memset(temp, 0, sizeof(temp));
for (int right = left; right < col; right++) {
for (int i = 0; i < row; i++)
temp[i] += mat[i][right];
sum = sum_k(temp, up, down, row, k);
area = (down - up + 1) * (right - left + 1);
if (sum && maxArea < area) {
final_point[0] = up;
final_point[1] = down;
final_point[2] = left;
final_point[3] = right;
maxArea = area;
}
}
}
if (final_point[0] == 0 && final_point[1] == 0 && final_point[2] == 0 &&
final_point[3] == 0 && mat[0][0] != k) {
cout << "No sub-matrix found";
return;
}
cout << "(Top, Left) Coordinate: " << "(" << final_point[0] << ", " << final_point[2] << ")" << endl;
cout << "(Bottom, Right) Coordinate: " << "(" << final_point[1] << ", " << final_point[3] << ")" << endl;
for (int j = final_point[0]; j <= final_point[1]; j++) {
for (int i = final_point[2]; i <= final_point[3]; i++)
cout << mat[j][i] << " ";
cout << endl;
}
}
main(){
vector<vector<int>> v = {
{ 2, 8, -5, 6 },
{ -7, 7, 8, -3 },
{ 11, -14, 4, 3 },
{ -4, 3, 1, 10 }};
sum_zero(v, 9);
}输入项
{{ 2, 8, -5, 6 },
{ -7, 7, 8, -3 },
{ 11, -14, 4, 3 },
{ -4, 3, 1, 10 }},
9输出结果
(Top, Left) Coordinate: (1, 0) (Bottom, Right) Coordinate: (3, 2) -7 7 8 11 -14 4 -4 3 1