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

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। हम पहले कॉलम को जितनी बार चाहें पुनर्व्यवस्थित कर सकते हैं, फिर केवल 1s वाले सबसे बड़े सबमैट्रिक्स का क्षेत्र लौटाएं।

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

1	0	0
1	1	1
1	0	1

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

1	0	0
1	1	1
1	1	0

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

n :=मैट्रिक्स की पंक्ति गणना
m :=मैट्रिक्स की कॉलम संख्या
उत्तर:=0
मैं के लिए 1 से n -1 की सीमा में, करो
- जे के लिए 0 से एम -1 की सीमा में, करो
  - यदि मैट्रिक्स [i, j] 1 है, तो
    - मैट्रिक्स[i, j] :=मैट्रिक्स[i, j] + मैट्रिक्स[i-1, j]
मैट्रिक्स में प्रत्येक पंक्ति के लिए, करें
- पंक्ति क्रमबद्ध करें
- j के लिए m-1 से 0 की सीमा में, 1 से घटाएं
  - उत्तर:=अधिकतम उत्तर और पंक्ति[j] *(m - j)
वापसी उत्तर

उदाहरण

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

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

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

इनपुट

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