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

একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে। কলামগুলো যেকোনোভাবে রিয়ারেঞ্জ করতে পারবেন। তারপর শুধু 1 ধারণকারী সবচেয়ে বড় সাবম্যাট্রিক্সের এলিয়া (এরিয়া) বের করতে হবে।

উদাহরণ:

1 0 0
1 1 1
1 0 1

1 0 0
1 1 1
1 1 0

সমাধানের পদ্ধতি

হিস্টোগ্রাম-ভিত্তিক DP পদ্ধতি (Largest Rectangle in Histogram-র biến形):

1. প্রতিটি সেলের জন্য উপরের সেল থেকে নিচে আসা কনsekutিভ 1-এর কাউন্ট ক্যালকুলেট করুন (হিস্টোগ্রাম হাইট)।
2. প্রতিটি সারিকে হিস্টোগ্রাম হিসেবে বিবেচনা করুন এবং সর্ট করুন।
3. সর্ট করা সারিতে, প্রতিটি হাইট h এর জন্য এলিয়া = h × (width) ক্যালকুলেট করুন।
4. সর্বোচ্চ এলিয়া ট্র্যাক করুন।

পাইথন কোড

def solve(matrix):
    n, m = len(matrix), len(matrix[0])
    ans = 0
    
    # প্রতিটি সেলের উপরে কতগুলো কনsekutিভ 1 আছে সেটি ক্যালকুলেট করুন
    for i in range(1, n):
        for j in range(m):
            if matrix[i][j] == 1:
                matrix[i][j] += matrix[i-1][j]
    
    # প্রতিটি সারি প্রক্রিয়া করুন
    for row in matrix:
        row.sort()  # হিস্টোগ্রাম সর্ট করুন
        for j in range(m-1, -1, -1):
            # row[j] = হাইট, (m - j) = 와ইডথ
            ans = max(ans, row[j] * (m - j))
    
    return ans

# টেস্ট
matrix = [
    [1, 0, 0],
    [1, 1, 1],
    [1, 0, 1]
]
print(solve(matrix))  # আউটপুট: 4

ব্যাখ্যা

সর্ট করার ফলে একই হাইটের বারগুলো একসাথে আসে। ডানদিক থেকে বামদিক স্ক্যান করলে row[j] * (m - j) দিয়ে ওই হাইটে সম্ভাব্য সর্বোচ্চ এলিয়া পাওয়া যায়।

সময় জটিলতা

O(n × m log m) - প্রতিটি সারি সর্ট করার কারণে। স্পেস O(1) এক্সট্রা (ইন-প্লেস মডিফিকেশন)।