পাইথনে কলাম পুনর্বিন্যাস দ্বারা বৃহত্তম সাবম্যাট্রিক্সের ক্ষেত্রফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। আমরা প্রথমে যতবার চাই ততবার কলামগুলিকে পুনর্বিন্যাস করতে পারি, তারপরে শুধুমাত্র 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 রেঞ্জের জন্য,
- করুন
  - যদি ম্যাট্রিক্স[i, j] 1 হয়, তাহলে
    - ম্যাট্রিক্স[i, j] :=ম্যাট্রিক্স[i, j] + ম্যাট্রিক্স[i-1, j]
ম্যাট্রিক্সের প্রতিটি সারির জন্য, করুন
- সারি সাজান
- m-1 থেকে 0 রেঞ্জের মধ্যে j-এর জন্য, 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]
]