Trong bài toán này, chúng ta được cung cấp một ma trận 2-D kích thước nXn bao gồm các số nhị phân (0/1). Nhiệm vụ của chúng tôi là tạo một chương trình để tìm Ma trận con tối đa có số lượng 1 nhiều hơn số 0.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
bin[N][N] = {
{0, 1, 0, 0},
{1, 1, 0, 0},
{1, 0, 1, 1},
{0, 1, 0, 1}
} Đầu ra
9
Giải thích
submatrix : bin[1][0], bin[1][1], bin[1][2] bin[2][0], bin[2][1], bin[2][2] bin[3][0], bin[3][1], bin[3][2] is the largest subarray with more 1’s one more than 0’s. Number of 0’s = 4 Number of 1’s = 5
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản là tìm tất cả các ma trận con có thể có từ ma trận và sau đó trả về diện tích tối đa cho tất cả.
Cách tiếp cận này dễ nghĩ và dễ thực hiện nhưng tốn rất nhiều thời gian và yêu cầu lồng các vòng lặp vào nhau khiến thứ tự O (n ^ 4) về thời gian trở nên phức tạp hơn. Vì vậy, hãy thảo luận về một phương pháp khác hiệu quả hơn.
Ý tưởng ở đây là cố định các cột ở bên trái và bên phải của ma trận và sau đó tìm mảng con lớn nhất có số lượng 0 nhiều hơn số 1. Chúng tôi sẽ tính tổng tại mỗi hàng và sau đó cộng dồn nó. Để tìm diện tích tối đa có số 1 nhiều hơn số 0.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int lenOfLongSubarr(int row[], int n, int& startInd, int& finishInd){
unordered_map<int, int> subArr;
int sumVal = 0, maxSubArrLen = 0;
for (int i = 0; i < n; i++) {
sumVal += row[i];
if (sumVal == 1) {
startInd = 0;
finishInd = i;
maxSubArrLen = i + 1;
}
else if (subArr.find(sumVal) == subArr.end())
subArr[sumVal] = i;
if (subArr.find(sumVal − 1) != subArr.end()) {
int currLen = (i − subArr[sumVal − 1]);
if (maxSubArrLen < currLen)
startInd = subArr[sumVal − 1] + 1;
finishInd = i;
maxSubArrLen = currLen;
}
}
return maxSubArrLen;
}
int largestSubmatrix(int bin[SIZE][SIZE], int n){
int rows[n], maxSubMatArea = 0, currArea, longLen, startInd,
finishInd;
for (int left = 0; left < n; left++) {
memset(rows, 0, sizeof(rows));
for (int right = left; right < n; right++) {
for (int i = 0; i < n; ++i){
if(bin[i][right] == 0)
rows[i] −= 1;
else
rows[i] += 1;
}
longLen = lenOfLongSubarr(rows, n, startInd, finishInd);
currArea = (finishInd − startInd + 1) * (right − left + 1);
if ((longLen != 0) && (maxSubMatArea < currArea)) {
maxSubMatArea = currArea;
}
}
}
return maxSubMatArea;
}
int main(){
int bin[SIZE][SIZE] = {
{ 1, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 0, 0 },
{ 0, 1, 0, 1 }
};
int n = 4;
cout<<"The maximum sub−matrix area having count of 1’s one more
than count of 0’s is "<<largestSubmatrix(bin, n);
return 0;
} Đầu ra
The maximum sub-matrix area having count of 1’s one more than count of 0’s is 9