Chương trình tìm diện tích của ma trận con lớn nhất theo cách sắp xếp lại cột trong Python

Giả sử chúng ta có một ma trận nhị phân. Trước tiên, chúng ta có thể sắp xếp lại các cột nhiều lần nếu chúng ta muốn, sau đó tìm trả về diện tích của submatrix lớn nhất chỉ chứa 1s.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 4, bởi vì chúng ta có thể sắp xếp giống như -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=số hàng của ma trận
• m:=số cột của ma trận
• ans:=0
• đối với tôi trong phạm vi từ 1 đến n - 1, thực hiện
  • đối với j trong phạm vi từ 0 đến m - 1, thực hiện
    • nếu ma trận [i, j] là 1, thì
      • matrix [i, j]:=matrix [i, j] + matrix [i-1, j]
• đối với mỗi hàng trong ma trận, thực hiện
  • sắp xếp hàng
  • cho j trong phạm vi m-1 đến 0, giảm 1, thực hiện
    • ans:=tối đa ans và row [j] * (m - j)
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

4