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

ধরুন আমাদের একটি m x n বাইনারি ম্যাট্রিক্স আছে, আমরা যে কোনো ক্রমে ম্যাট্রিক্সের কলামগুলোকে পুনরায় সাজাতে পারি। আমাদের ম্যাট্রিক্সের মধ্যে বৃহত্তম সাবম্যাট্রিক্সের ক্ষেত্রফল খুঁজে বের করতে হবে যেখানে কিছু পুনর্বিন্যাস কাজ সম্পাদন করার পরে সাবম্যাট্রিক্সের প্রতিটি উপাদান 1 হয়।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 4 কারণ, কলাম অদলবদল করার পর আমরা ম্যাট্রিক্স পাচ্ছি যেমন

এখানে সর্বাধিক সাবম্যাট্রিক্স চার 1 এর সাথে বর্গাকার আকারের।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• সারি :=ম্যাট্রিক্সের সারির সংখ্যা, col :=ম্যাট্রিক্সের কলামের সংখ্যা
0 থেকে col - 1 পরিসরে j-এর জন্য
• করুন
  • আমি 1 থেকে সারি - 1 রেঞ্জের জন্য, কর
    • যদি ম্যাট্রিক্স[i, j] 1 হয়, তাহলে
      • ম্যাট্রিক্স[i, j] :=ম্যাট্রিক্স[i, j] + ম্যাট্রিক্স[i-1, j]
• উত্তর :=0
• আমি 0 থেকে সারি - 1 এর মধ্যে, কর
  • তালিকা ম্যাট্রিক্স সাজান[i]
  col-1 থেকে 0 রেঞ্জের মধ্যে j-এর জন্য
  • , 1 কমিয়ে
    করুন
    • যদি ম্যাট্রিক্স[i, j] 0 এর মত হয়, তাহলে
      • লুপ থেকে বেরিয়ে আসুন
      • উত্তর =সর্বাধিক উত্তর এবং (col-j)*ম্যাট্রিক্স[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