โปรแกรมหาพื้นที่ Submatrix ใหญ่สุดโดยการจัดเรียงคอลัมน์ใน Python

สมมติมี Binary Matrix สามารถจัดเรียงคอลัมน์ได้ไม่จำกัดครั้ง แล้วหาพื้นที่ Submatrix ใหญ่สุดที่ประกอบด้วย 1 เท่านั้น

ตัวอย่าง Input:

1	0	0
1	1	1
1	0	1

Output: 4 เพราะจัดเรียงได้เป็น:

1	0	0
1	1	1
1	1	0

ขั้นตอนการแก้ปัญหา

n := จำนวนแถว m := จำนวนคอลัมน์ ans := 0
Loop i = 1 ถึง n-1: Loop j = 0 ถึง m-1: ถ้า matrix[i][j] == 1 ให้ matrix[i][j] += matrix[i-1][j]
Loop ทุก Row: เรียง Row แล้ว Loop j = m-1 ถึง 0: ans = max(ans, row[j] * (m - j))
Return ans

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

def solve(matrix): 
    n, m = len(matrix), len(matrix[0]) 
    ans = 0 
    for i in range(1, n): 
        for j in range(m): 
            if matrix[i][j]: 
                matrix[i][j] += matrix[i-1][j] 
    for row in matrix: 
        row.sort() 
        for j in range(m-1, -1, -1): 
            ans = max(ans, row[j] * (m - j)) 
    return ans 

matrix = [[1, 0, 0], [1, 1, 1], [1, 0, 1]] 
print(solve(matrix))

Input

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