Chương trình tìm ma trận con lớn nhất sau sắp xếp cột trong Python

Mô tả bài toán

Cho ma trận nhị phân m x n. Có thể sắp xếp lại thứ tự cột tùy ý. Tìm diện tích ma trận con toàn số 1 lớn nhất sau khi sắp xếp cột.

Ví dụ

Ma trận:

0 0 1
1 1 1
1 0 1

Giải thuật

1. Tính chiều cao cột liên tiếp 1: matrix[i][j] += matrix[i-1][j] nếu matrix[i][j] == 1.
2. Với mỗi hàng, sắp xếp các chiều cao giảm dần.
3. Duyệt từ phải sang trái: diện tích = (col - j) * matrix[i][j], cập nhật max.

Triển khai Python

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

Đầu vào

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

Đầu ra

4