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

สมมติว่าเรามีเมทริกซ์ไบนารี m x n เราสามารถจัดเรียงคอลัมน์ของเมทริกซ์ในลำดับใดก็ได้ เราต้องหาพื้นที่ของเมทริกซ์ย่อยที่ใหญ่ที่สุดภายในเมทริกซ์โดยที่ทุกองค์ประกอบของเมทริกซ์ย่อยเป็น 1 หลังจากดำเนินการจัดลำดับใหม่บางอย่าง

ดังนั้นหากอินพุตเป็นแบบ

1	0	1
1	1	1

ผลลัพธ์จะเป็น 4 เพราะหลังจากการสลับคอลัมน์เราได้รับเมทริกซ์เช่น

1	1	0
1	1	1
0	1	0

เมทริกซ์ย่อยสูงสุดที่นี่มีขนาดสี่เหลี่ยมจัตุรัสโดยมี 1 สี่ตัว

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

แถว :=จำนวนแถวของเมทริกซ์, col :=จำนวนคอลัมน์ของเมทริกซ์
สำหรับ j ในช่วง 0 ถึง col - 1 ทำ
- สำหรับฉันในช่วง 1 ถึงแถว - 1 ทำ
  - ถ้าเมทริกซ์[i, j] เป็น 1 แล้ว
    - เมทริกซ์[i, j] :=เมทริกซ์[i, j] + เมทริกซ์[i-1, j]
ตอบ :=0
สำหรับฉันในช่วง 0 ถึงแถว - 1 ทำ
- เรียงลำดับเมทริกซ์รายการ[i]
- สำหรับ j ในช่วง col-1 ถึง 0, ลดลง 1 ทำ
  - ถ้าเมทริกซ์[i, j] เท่ากับ 0 แล้ว
    - ออกมาจากวงจร
    - ans =สูงสุดของ ans และ (col-j)*matrix[i, j])
คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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