สมมติว่าเรามีเมทริกซ์ไบนารี ต้องการหาสี่เหลี่ยมผืนผ้าขนาดใหญ่ที่สุดที่ประกอบด้วย 1 ทั้งหมด โดยอนุญาตให้สลับคอลัมน์ได้ทุกคู่
เช่น เมทริกซ์ 3x5 ตัวอย่าง ผลลัพธ์คือ 6 โดยสลับคอลัมน์ 1 กับ 3
ขั้นตอนการแก้ปัญหา
- สร้างเมทริกซ์
tempเก็บความสูงของ 1 ต่อเนื่องในแต่ละคอลัมน์ - สำหรับแต่ละแถว เรียงคอลัมน์ตามความสูงจากมากไปน้อย
- คำนวณพื้นที่สี่เหลี่ยมผืนผ้าสูงสุด:
area = (j+1) * temp[i][j]
ตัวอย่างโค้ด Python
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):
for i in range(col):
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 = (j + 1) * temp[i][j]
if area > area_max:
area_max = area
return area_max
mat = [
[0, 0, 1, 1, 0],
[0, 0, 1, 1, 1],
[1, 0, 1, 1, 0]
]
print("Area:", maxArea(mat))
อินพุต
[[1, 0, 0, 1, 0], [1, 0, 0, 1, 1], [1, 1, 0, 1, 0]]
เอาต์พุต
Area: 6
