พื้นที่ซับเมทริกซ์สูงสุดที่จำนวน 1 มากกว่าจำนวน 0 เพียง 1 ในโปรแกรม C++

ในปัญหานี้ เราได้รับเมทริกซ์ 2 มิติขนาด n x n ที่ประกอบด้วยตัวเลขไบนารี (0/1) ภารกิจของเราคือสร้างโปรแกรมเพื่อหาพื้นที่ซับเมทริกซ์สูงสุดที่จำนวน 1 มากกว่าจำนวน 0 เพียง 1

ตัวอย่าง

อินพุต

bin[N][N] = { 
    {0, 1, 0, 0}, 
    {1, 1, 0, 0}, 
    {1, 0, 1, 1}, 
    {0, 1, 0, 1} 
}

เอาต์พุต

9

คำอธิบาย

ซับเมทริกซ์: 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] 
เป็นซับอาร์เรย์ที่ใหญ่ที่สุดที่มี 1 มากกว่า 0 เพียง 1 
จำนวน 0 = 4 
จำนวน 1 = 5

แนวทางแก้ปัญหา

วิธีแก้ที่ง่ายคือการหาซับเมทริกซ์ทั้งหมดที่เป็นไปได้จากเมทริกซ์แล้วคืนค่าพื้นที่สูงสุดจากทั้งหมด

วิธีนี้ง่ายต่อการคิดและนำไปใช้แต่ใช้เวลามากและต้องการการซ้อนลูปทำให้ความซับซ้อนของเวลาเป็นออเดอร์ O(n^4) ดังนั้นมาพูดถึงวิธีอีกวิธีที่มีประสิทธิภาพมากกว่า

แนวคิดที่นี่คือการกำหนดคอลัมน์ซ้ายและขวาของเมทริกซ์ แล้วหาซับอาร์เรย์ที่ใหญ่ที่สุดซึ่งมีจำนวน 0 มากกว่าจำนวน 1 เพียง 1 เราจะคำนวณผลรวมที่แต่ละแถวแล้วสะสมมัน เพื่อหาพื้นที่สูงสุดที่มีจำนวน 1 มากกว่าจำนวน 0 เพียง 1

ตัวอย่างโค้ด

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#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