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

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

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

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

एल्गोरिदम

1. n := मैट्रिक्स की पंक्ति संख्या
2. m := मैट्रिक्स की कॉलम संख्या
3. ans := 0
4. प्रत्येक पंक्ति i के लिए 1 से n-1 तक:
   • प्रत्येक कॉलम j के लिए 0 से m-1 तक:
     • यदि matrix[i][j] == 1, तो matrix[i][j] += matrix[i-1][j]
5. प्रत्येक पंक्ति के लिए मैट्रिक्स में:
   • पंक्ति को सॉर्ट करें
   • j के लिए m-1 से 0 तक घटते क्रम में:
     • ans = max(ans, row[j] * (m - j))
6. ans लौटाएं

उदाहरण कार्यान्वयन

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))  # आउटपुट: 4

इनपुट

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

आउटपुट

4