Tìm hình chữ nhật lớn nhất toàn 1 với cho phép hoán đổi cột trong Python

Cho ma trận nhị phân, tìm diện tích hình chữ nhật toàn 1 lớn nhất. Có thể hoán đổi vị trí các cột tùy ý.

Ví dụ: ma trận 3x5 cho trước → kết quả 6 (sau khi hoán đổi cột).

Giải thuật

• Tính mảng temp[i][j] = số lượng 1 liên tiếp kết thúc tại hàng i, cột j (tính theo cột).
• Với mỗi hàng, đếm tần suất các giá trị trong temp, sau đó sắp xếp giảm dần (mô phỏng hoán đổi cột).
• Tính diện tích: với cột thứ j (0-based), chiều cao = temp[i][j], chiều rộng = j+1. Diện tích = (j+1) * temp[i][j].
• Lấy max diện tích.

Ví dụ

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))

Đầu vào

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

Đầu ra

Area : 2