สมมติว่าเรามีเมทริกซ์ไบนารี เราต้องหาสี่เหลี่ยมที่ใหญ่ที่สุดของทั้งหมด 1 ในเมทริกซ์ที่กำหนด สี่เหลี่ยมผืนผ้าสามารถสร้างได้โดยการสลับหรือแลกเปลี่ยนคู่ของคอลัมน์ของเมทริกซ์นั้น
ดังนั้นหากอินพุตเป็นแบบ
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
แล้วผลลัพธ์จะเป็น 6 ในกรณีนี้ สี่เหลี่ยมผืนผ้าสามารถสร้างได้โดยการแลกเปลี่ยนคอลัมน์ 1 กับ 3 เมทริกซ์หลังการแลกเปลี่ยนจะเป็น -
| 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 |
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
แถว :=ขนาดของเสื่อ
-
col :=ขนาดของเสื่อ[0]
-
temp :=เมทริกซ์ของคำสั่ง (แถว + 1) x (col + 1) และเติมด้วย 0
-
สำหรับผมอยู่ในช่วง 0 ถึง col ทำ
-
temp[0, i] :=mat[0, i]
-
สำหรับ j ในช่วง 1 ถึงแถว ทำ
-
ถ้า mat[j, i] เท่ากับ 0 แล้ว
-
อุณหภูมิ[j, i] :=0
-
-
มิฉะนั้น
-
temp[j, i] :=temp[j - 1, i] + 1
-
-
-
-
สำหรับผมอยู่ในช่วง 0 ถึงแถว ทำ
-
cnt :=ขนาดอาร์เรย์ (แถว + 1) และเติม 0
-
สำหรับ j ในช่วง 0 ถึง col เพิ่มขึ้น 1 ทำ
-
cnt[temp[i, j]] :=cnt[temp[i, j]] + 1
-
-
col_no :=0
-
j :=แถว
-
ในขณะที่ j>=0 ทำ
-
ถ้า cnt[j]> 0 แล้ว
-
สำหรับ k ในช่วง 0 ถึง cnt[j] ทำ
-
temp[i, col_no] :=j
-
col_no :=col_no + 1
-
-
-
เจ :=เจ - 1
-
-
-
area_maximum :=0
-
สำหรับผมอยู่ในช่วง 0 ถึงแถว ทำ
-
สำหรับ j ในช่วง 0 ถึง col ทำ
-
area_current :=(j + 1) * อุณหภูมิ[i, j]
-
ถ้า area_current> area_maximum แล้ว
-
area_maximum :=พื้นที่_กระแส
-
-
-
-
พื้นที่ส่งคืน_สูงสุด
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def maxArea(mat):
row = len(mat)
col = len(mat[0])
temp = [[0 for i in range(col + 1)] for i in range(row + 1)]
for i in range(0, col):
temp[0][i] = mat[0][i]
for j in range(1, row):
if ((mat[j][i] == 0)):
temp[j][i] = 0
else:
temp[j][i] = temp[j - 1][i] + 1
for i in range(0, row):
cnt = [0 for i in range(row + 1)]
for j in range(0, col, 1):
cnt[temp[i][j]] += 1
col_no = 0
j = row
while(j >= 0):
if (cnt[j] > 0):
for k in range(0, cnt[j]):
temp[i][col_no] = j
col_no += 1
j -= 1
area_maximum = 0
for i in range(0, row):
for j in range(0, col):
area_current = (j + 1) * temp[i][j]
if (area_current > area_maximum):
area_maximum = area_current
return area_maximum
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 : 2
