পাইথনে কলাম সওয়াপ (swap) অনুমত থাকলে ১-র সবচেয়ে বড় রেক্ট্যাঙ্গেল খুঁজে বের করা

একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে। কলামগুলো আপস করা যেতে পারে। কলাম সওয়াপ করে ১-র সবচেয়ে বড় রেক্ট্যাঙ্গেল (submatrix) বের করতে হবে।

উদাহরণ

ইনপুট ম্যাট্রিক্স: [[1,0,0,1,0], [1,0,0,1,1], [1,1,0,1,0]]

কলাম ১ ও ৩ সওয়াপ করলে: [[0,0,1,1,0], [0,0,1,1,1], [1,0,1,1,0]]

সর্বোচ্চ রেক্ট্যাঙ্গেল আকার = ৬

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

1. প্রতিটি কলামের জন্য 上面 থেকে নিচে পর্যন্ত লগাতার ১-এর সংখ্যা গণনা করুন (হিস্টোগ্রাম 높이)।
2. প্রতিটি সারির হিস্টোগ্রাম হাইটগুলো সাজান (descending)।
3. সাজানো হাইটের জন্য, (ইনডেক্স+১) × হাইট = রেক্ট্যাঙ্গেল আকার।
4. সর্বোচ্চ আকার বের করুন।

পাইথন কোড

def maxArea(mat):
    row = len(mat)
    col = len(mat[0])
    temp = [[0] * (col + 1) for _ in range(row + 1)]
    
    for i in range(col):
        temp[0][i] = mat[0][i]
        for j in range(1, row):
            if mat[j][i] == 0:
                temp[j][i] = 0
            else:
                temp[j][i] = temp[j-1][i] + 1
    
    for i in range(row):
        cnt = [0] * (row + 1)
        for j in range(col):
            cnt[temp[i][j]] += 1
        col_no = 0
        j = row
        while j >= 0:
            if cnt[j] > 0:
                for _ in range(cnt[j]):
                    temp[i][col_no] = j
                    col_no += 1
            j -= 1
    
    area_max = 0
    for i in range(row):
        for j in range(col):
            area_current = (j + 1) * temp[i][j]
            if area_current > area_max:
                area_max = area_current
    return area_max

mat = [
    [0, 0, 1, 1, 0],
    [0, 0, 1, 1, 1],
    [1, 0, 1, 1, 0]
]
print("Area:", maxArea(mat))

ইনপুট

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

আউটপুট

Area: 6