ในปัญหานี้ เราได้รับเมทริกซ์ 2 มิติขนาด nXn ซึ่งประกอบด้วยเลขฐานสอง (0/1) งานของเราคือสร้างโปรแกรมเพื่อค้นหาเมทริกซ์ย่อยสูงสุดที่มีการนับของ 1 มากกว่าการนับ 0
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
bin[N][N] = {
{0, 1, 0, 0},
{1, 1, 0, 0},
{1, 0, 1, 1},
{0, 1, 0, 1}
} ผลลัพธ์
9
คำอธิบาย
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
แนวทางการแก้ปัญหา
วิธีง่ายๆ คือ ค้นหาเมทริกซ์ย่อยทั้งหมดที่เป็นไปได้จากเมทริกซ์ แล้วคืนค่าพื้นที่สูงสุดออกจากทั้งหมด
วิธีนี้ง่ายต่อการคิดและนำไปใช้ แต่ต้องใช้เวลามากและต้องใช้การวนซ้ำที่ทำให้เวลาของลำดับมีความซับซ้อน O(n^4) .เอาล่ะ มาพูดถึงอีกวิธีหนึ่งที่ได้ผลดีกว่ากัน
แนวคิดในที่นี้คือการแก้ไขคอลัมน์ทางด้านซ้ายและด้านขวาของเมทริกซ์ จากนั้นให้หาอาร์เรย์ย่อยที่ใหญ่ที่สุดซึ่งมีจำนวน 0 มากกว่าจำนวน 1 เราจะคำนวณผลรวมในแต่ละแถวแล้วสะสม การหาพื้นที่สูงสุดที่มีการนับ 1 มากกว่า 0
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The maximum sub-matrix area having count of 1’s one more than count of 0’s is 9
