Python - Diện tích ma trận con lớn nhất sau khi sắp xếp cột

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

Ví dụ

Input:
1 0 0
1 1 1
1 0 1

Sắp xếp cột tối ưu:
1 0 0
1 1 1  ← hàng 2,3 cột 1,2 tạo khối 2x2 = 4
1 1 0

Output: 4

Thuật toán: Histogram + Sắp xếp hàng

1. Xây dựng "độ cao" histogram: matrix[i][j] += matrix[i-1][j] nếu matrix[i][j] == 1 (số 1 liên tiếp từ trên xuống)
2. Với mỗi hàng: sắp xếp hàng giảm dần (giả lập sắp xếp cột toàn cục)
3. Với hàng đã sắp xếp: diện tích max = max(row[j] * (m - j)) (chiều cao × chiều rộng từ j đến cuối)

Mã Python

def solve(matrix):
    n, m = len(matrix), len(matrix[0])
    ans = 0
    
    # Xây dựng histogram độ cao cột 1 liên tiếp
    for i in range(1, n):
        for j in range(m):
            if matrix[i][j]:
                matrix[i][j] += matrix[i-1][j]
    
    # Mỗi hàng: sắp xếp và tính diện tích max
    for row in matrix:
        row.sort()
        for j in range(m-1, -1, -1):
            ans = max(ans, row[j] * (m - j))
    
    return ans

# Test
matrix = [
    [1, 0, 0],
    [1, 1, 1],
    [1, 0, 1]
]
print(solve(matrix))  # Output: 4

Giải thích trực quan

Sau khi xây dựng histogram:

Hàng 0: [1, 0, 0]
Hàng 1: [2, 1, 1]  ← 1+1, 0+1, 0+1
Hàng 2: [3, 0, 2]  ← 2+1, 1+0, 1+1

Sắp xếp hàng 2: [3, 2, 0] → diện tích: 3×1=3, 2×2=4, 0×3=0 → max=4.

Phân tích độ phức tạp

• Thời gian: O(n × m log m) - sắp xếp mỗi hàng
• Không gian: O(1) thêm (sửa đổi ma trận gốc)

Bài toán gốc: LeetCode 1727 - Largest Submatrix With Rearrangements.