পাইথনে কলাম রি-অর্ডারিং দিয়ে সর্বোচ্চ সাবম্যাট্রিক্স খুঁজে বের করার প্রোগ্রাম

আমাদের একটি m x n বাইনারি ম্যাট্রিক্স আছে, আমরা ম্যাট্রিক্সের কলামগুলো যেকোনো ক্রমে রি-অর্ডার করতে পারি। আমাদের ম্যাট্রিক্সের ভিতরে এমন সবচেয়ে বড় সাবম্যাট্রিক্সের এরিয়া বের করতে হবে যেটির সব উপাদান ১ রি-অর্ডার করার পর।

উদাহরণস্বরূপ, ইনপুট ম্যাট্রিক্স:

হলে আউটপুট হবে 4 কারণ, কলাম সোয়াপ করার পর ম্যাট্রিক্স যেন:

এখানে সর্বাধিক সাবম্যাট্রিক্স ৪টি ১-র বর্গাকার।

সমাধানের ধাপসমূহ

• row := ম্যাট্রিক্সের রো সংখ্যা, col := কলাম সংখ্যা

• j = 0 থেকে col-1 পর্যন্ত লুপ চালান:

  • i = 1 থেকে row-1 পর্যন্ত লুপ চালান:

    • যদি matrix[i][j] == 1 হয়, তবে matrix[i][j] += matrix[i-1][j]

• ans := 0

• i = 0 থেকে row-1 পর্যন্ত লুপ চালান:

  • matrix[i] সর্ট করুন

  • j = col-1 থেকে ০ পর্যন্ত ১ কমানো হারে লুপ চালান:

    • যদি matrix[i][j] == 0 হয়, তবে ব্রেক করুন

    • ans = max(ans, (col-j) * matrix[i][j])

• ans রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

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