파이썬에서 열 재배열로 가장 큰 부분행렬의 면적을 찾는 프로그램

이진 행렬이 있다고 가정합니다. 먼저 열을 원하는 만큼 재정렬한 다음 반환값이 1만 포함된 가장 큰 부분행렬의 면적을 찾을 수 있습니다.

따라서 입력이 다음과 같으면

다음과 같이 정렬할 수 있기 때문에 출력은 4가 됩니다. -

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=행렬의 행 수
• m :=행렬의 열 개수
• ans :=0
• 1 ~ n - 1 범위의 i에 대해
  • 0 ~ m - 1 범위의 j에 대해
    • 행렬[i, j]가 1이면
      • 행렬[i, j] :=행렬[i, j] + 행렬[i-1, j]
• 행렬의 각 행에 대해 다음을 수행합니다.
  • 행 정렬
  • m-1 ~ 0 범위의 j에 대해 1 감소, do
    • ans :=ans 및 row[j]의 최대값 *(m - j)
• 반환

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

입력

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

출력

4