Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सभी 1 वाले अधिकतम आकार के आयताकार बाइनरी सब-मैट्रिक्स


इस ट्यूटोरियल में, हम सभी 1 वाले अधिकतम आकार के आयताकार बाइनरी सब-मैट्रिक्स को खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।

इसके लिए हमें शून्य और एक वाली 2D मैट्रिक्स प्रदान की जाएगी। हमारा कार्य केवल 1 वाले सबसे बड़े 2D मैट्रिक्स सबसेट को ढूंढना है।

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
#define R 4 
#define C 4 
// अधिकतम क्षेत्र ढूंढना 
int maxHist(int row[]) { 
    stack<int> result; 
    int top_val; 
    int max_area = 0; 
    int area = 0; 
    int i = 0; 
    while (i < C) { 
        if (result.empty() || row[result.top()] <= row[i]) 
            result.push(i++); 
        else { 
            top_val = row[result.top()]; 
            result.pop(); 
            area = top_val * i; 
            if (!result.empty()) 
                area = top_val * (i - result.top() - 1); 
            max_area = max(area, max_area); 
        } 
    } 
    while (!result.empty()) { 
        top_val = row[result.top()]; 
        result.pop(); 
        area = top_val * i; 
        if (!result.empty()) 
            area = top_val * (i - result.top() - 1); 
        max_area = max(area, max_area); 
    } 
    return max_area; 
} 
// आवश्यक सबसेट का क्षेत्र वापस करना 
int maxRectangle(int A[][C]) { 
    int result = maxHist(A[0]); 
    for (int i = 1; i < R; i++) { 
        for (int j = 0; j < C; j++) 
            if (A[i][j]) 
                A[i][j] += A[i - 1][j]; 
        result = max(result, maxHist(A[i])); 
    } 
    return result; 
} 
int main() { 
    int A[][C] = { 
        { 0, 1, 1, 0 },
        { 1, 1, 1, 1 },
        { 1, 1, 1, 1 },
        { 1, 1, 0, 0 }, 
    }; 
    cout << "Area of maximum rectangle is " << maxRectangle(A); 
    return 0; 
}

आउटपुट

Area of maximum rectangle is 8
  1. - C++ में बाइनरी ट्री की अधिकतम चौड़ाई

    समस्या विवरणएक बाइनरी ट्री दिया गया है, दिए गए ट्री की अधिकतम चौड़ाई प्राप्त करने के लिए एक फंक्शन लिखें। ट्री की चौड़ाई सभी स्तरों की चौड़ाई का अधिकतम है।नीचे दिए गए ट्री पर विचार करें −      10      / \     7   4    / \   \   9

  1. - C++ में दिए गए योग के साथ अधिकतम आकार का सबसेट

    समस्या कथनN तत्वों का एक एरे और योग दिया गया है। हमें उस अधिकतम आकार के सबसेट का आकार ढूंढना है जिसका योग दिए गए योग के बराबर हो।उदाहरणयदि इनपुट एरे arr = { 2, 3, 5, 10 } है और योग = 20 है तो आउटपुट 4 होगा क्योंकि −2 + 3 + 5 + 10 = 20 जो दिए गए योग के बराबर है।एल्गोरिदमहम इस समस्या को हल करने

  1. - C++ में योग शून्य वाले सभी उपसरणी (Subarrays) प्रिंट करें

    इस समस्या में, हमें पूर्णांक मानों की एक सरणी दी गई है और हमें इस सरणी से उन सभी उपसरणी को प्रिंट करना है जिनका योग 0 के बराबर है। विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं, इनपुट: सरणी = [-5, 0, 2, 3, -3, 4, -1] आउटपुट: इंडेक्स 1 से 4 तक उपसरणी का योग 0 है। इंडेक्स 5 से 7 तक उपसरणी का यो