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

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

तो, अगर इनपुट पसंद है

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

यहां अधिकतम सबमैट्रिक्स चार 1 के साथ चौकोर आकार का है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• पंक्ति:=मैट्रिक्स की पंक्तियों की संख्या, कॉलम:=मैट्रिक्स के स्तंभों की संख्या
• जे के लिए 0 से col-1 की श्रेणी में, do
  • 1 से पंक्ति -1 की श्रेणी में i के लिए
    • यदि मैट्रिक्स [i, j] 1 है, तो
      • मैट्रिक्स[i, j] :=मैट्रिक्स[i, j] + मैट्रिक्स[i-1, j]
• उत्तर:=0
• मैं के लिए 0 से पंक्ति -1 की सीमा में, करो
  • सूची मैट्रिक्स को क्रमबद्ध करें[i]
  • जे के लिए col-1 से 0 की श्रेणी में, 1 से घटाएं
    • यदि मैट्रिक्स [i, j] 0 के समान है, तो
      • लूप से बाहर आएं
      • Ans =अधिकतम उत्तर और (col-j)*matrix[i, j])
• वापसी उत्तर

उदाहरण

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

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