Giả sử chúng ta có một ma trận 2D và giá trị K, chúng ta phải tìm ma trận con hình chữ nhật dài nhất có tổng bằng K.
Vì vậy, nếu đầu vào giống như
| 2 | 8 | - 5 | 6 |
| - 7 | 7 | 8 | - 3 |
| 11 | - 14 | 4 | 3 |
| - 4 | 3 | 1 | 10 |
Và K =9
thì đầu ra sẽ là điểm Trên cùng bên trái là (1, 0) và điểm Dưới cùng bên phải là (3, 2).
| - 7 | 7 | 8 |
| 11 | - 14 | 4 |
| - 4 | 3 | 1 |
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
-
TỐI ĐA:=100
-
Xác định một hàm sum_k (), hàm này sẽ lấy một mảng arr, start, end, n, k,
-
Xác định một bản đồ
-
sum:=0, Maximum_length:=0
-
để khởi tạo i:=0, khi i
-
sum:=sum + arr [i]
-
nếu tổng bằng k, thì -
-
max_length:=i + 1
-
bắt đầu:=0
-
end:=i
-
-
nếu tổng không có trong bản đồ, thì -
-
bản đồ [sum]:=i
-
-
nếu (sum - k) có trong bản đồ, thì -
-
nếu Maximum_length <(i - map [sum - k]), thì -
-
Maximum_length:=i - map [sum - k]
-
start:=map [sum - k] + 1
-
end:=i
-
-
-
-
trả về true khi Maximum_length không phải là 0
-
Từ phương thức chính, thực hiện như sau -
-
row:=số hàng của tấm lót, col:=số cột của tấm lót
-
Xác định nhiệt độ mảng có kích thước:hàng.
-
Xác định một mảng final_point ={0,0,0,0}
-
maxArea:=-inf
-
để khởi tạo left:=0, khi left
-
lấp đầy nhiệt độ bằng 0
-
để khởi tạo right:=left, khi right
-
để khởi tạo i:=0, khi i
-
temp [i]:=temp [i] + mat [i, right]
-
-
sum:=sum_k (tạm thời, lên, xuống, hàng, k)
-
vùng:=(xuống - lên + 1) * (phải - trái + 1)
-
nếu tổng khác 0 và maxArea
-
final_point [0]:=up, final_point [1]:=down
-
final_point [2]:=left, final_point [3]:=right
-
maxArea:=area
-
-
-
nếu final_point là [0,0,0,0] và mat [0,0] không phải là k, thì
-
trả về "Không tìm thấy ma trận con"
-
-
-
hiển thị điểm trên cùng bên trái (final_point [0], final_point [2])
-
hiển thị điểm dưới cùng bên phải (điểm cuối cùng [1], điểm cuối cùng [3])
-
các phần tử chiếu.
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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);
} Đầu vào
{{ 2, 8, -5, 6 },
{ -7, 7, 8, -3 },
{ 11, -14, 4, 3 },
{ -4, 3, 1, 10 }},
9 Đầu ra
(Top, Left) Coordinate: (1, 0) (Bottom, Right) Coordinate: (3, 2) -7 7 8 11 -14 4 -4 3 1