Chương trình tìm ma trận con lớn nhất với sự sắp xếp lại bằng Python

Giả sử chúng ta có một ma trận nhị phân m x n, chúng ta có thể sắp xếp lại các cột của ma trận theo thứ tự bất kỳ. Chúng ta phải tìm diện tích của ma trận con lớn nhất trong ma trận mà mọi phần tử của ma trận con là 1 sau khi thực hiện một số tác vụ sắp xếp lại.

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

thì đầu ra sẽ là 4 vì sau khi hoán đổi cột, chúng ta sẽ nhận được ma trận như

ở đây submatrix tối đa có kích thước hình vuông với bốn chữ 1.

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

• row:=số hàng của ma trận, col:=số cột của ma trận
• đối với j trong phạm vi 0 đến col - 1, thực hiện
  • đối với tôi trong phạm vi từ 1 đến hàng - 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]
• ans:=0
• đối với tôi trong phạm vi từ 0 đến hàng - 1, thực hiện
  • sắp xếp ma trận danh sách [i]
  • cho j trong phạm vi col-1 đến 0, giảm 1, thực hiện
    • nếu ma trận [i, j] giống 0, thì
      • ra khỏi vòng lặp
      • ans =tối đa ans và (col-j) * ma trận [i, 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):
   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))

Đầu vào

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

Đầu ra

4