โปรแกรมหาซับแมทริกซ์ใหญ่สุดหลังจัดเรียงคอลัมน์ใน Python

มีเมทริกซ์ไบนารี m×n สามารถเรียงคอลัมน์ได้อย่างไรก็ตาม หาพื้นที่ซับแมทริกซ์ที่เป็น 1 ทั้งหมดใหญ่สุด

ตัวอย่าง: เมทริกซ์ 3×3 ผลลัพธ์ 4 (หลังสลับคอลัมน์ได้ 2×2 ทั้งหมดเป็น 1)

วิธีแก้ปัญหา

1. คำนวณความสูงสะสม (histogram) ทุกคอลัมน์: matrix[i][j] += matrix[i-1][j] ถ้าเป็น 1
2. แต่ละแถว เรียงคอลัมน์จากน้อยไปมาก
3. คำนวณพื้นที่สี่เหลี่ยม: (col-j) * matrix[i][j] สำหรับคอลัมน์ที่ไม่เป็น 0
4. หาค่าสูงสุด

ตัวอย่างโค้ด

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

อินพุต

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

เอาต์พุต

4