पायथन में रिअरेंजमेंट के साथ सबसे बड़ा सबमैट्रिक्स खोजने का प्रोग्राम

मान लीजिए हमारे पास एक m x n बाइनरी मैट्रिक्स है, हम मैट्रिक्स के कॉलम को किसी भी क्रम में रिअरेंज कर सकते हैं। हमें मैट्रिक्स के भीतर सबसे बड़े सबमैट्रिक्स का क्षेत्रफल ढूंढना है जहां कुछ रिऑर्डरिंग करने के बाद सबमैट्रिक्स का हर एलिमेंट 1 हो।

उदाहरण के लिए, यदि इनपुट है:

तो आउटपुट 4 होगा क्योंकि, कॉलम स्वैप करने के बाद हमें मैट्रिक्स मिलता है:

यहां अधिकतम सबमैट्रिक्स चार 1's के साथ वर्गाकार आकार का है।

हल करने के चरण

1. row := मैट्रिक्स की पंक्ति संख्या, col := मैट्रिक्स की कॉलम संख्या
2. j को 0 से col - 1 तक लूप चलाएं:
   • i को 1 से row - 1 तक लूप चलाएं:
     • यदि matrix[i][j] == 1, तो matrix[i][j] := matrix[i][j] + matrix[i-1][j]
3. ans := 0
4. i को 0 से row - 1 तक लूप चलाएं:
   • matrix[i] सूची को सॉर्ट करें
   • j को col-1 से 0 तक घटाते हुए लूप चलाएं:
     • यदि matrix[i][j] == 0, तो लूप से बाहर निकलें
     • ans = max(ans, (col-j) * matrix[i][j])
5. ans वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(matrix):
    row, col = len(matrix), len(matrix[0])
    for j in range(col):
        for i in range(1, row):
            if matrix[i][j]:
                matrix[i][j] += matrix[i-1][j]
    ans = 0
    for i in range(row):
        matrix[i].sort()
        for j in range(col-1, -1, -1):
            if matrix[i][j] == 0:
                break
            ans = max(ans, (col-j) * matrix[i][j])
    return ans

matrix = [[0,0,1],[1,1,1],[1,0,1]]
print(solve(matrix))

इनपुट

[[0,0,1],[1,1,1],[1,0,1]]

आउटपुट

4