Pythonで再配置された最大の部分行列を見つけるプログラム

m x nのバイナリ行列があるとすると、行列の列を任意の順序で再配置できます。いくつかの並べ替えタスクを実行した後、サブマトリックスのすべての要素が1である、マトリックス内の最大のサブマトリックスの領域を見つける必要があります。

したがって、入力が次のような場合

列を交換した後、

ここで、最大部分行列は4つの1を含む正方形のサイズです。

これを解決するには、次の手順に従います-

• row：=行列の行数、col：=行列の列数
• 0からcol-1の範囲のjの場合、do
  • iの範囲が1から行-1の場合、実行します
    • matrix [i、j]が1の場合、
      • matrix [i、j]：=matrix [i、j] + matrix [i-1、j]
• ans：=0
• 0から行-1の範囲のiの場合、実行
  • リストマトリックスを並べ替える[i]
  • col-1から0の範囲のjの場合、1ずつ減らします。
    • matrix [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]]

出力

4