Pythonの列の再配置によって最大の部分行列の領域を見つけるプログラム

バイナリ行列があるとします。最初に列を必要な回数だけ再配置してから、1のみを含む最大の部分行列の領域を返すことができます。

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

配置できるので、出力は4になります-

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

• n：=行列の行数
• m：=行列の列数
• ans：=0
• 1からn-1の範囲のiの場合、do
  • 0〜m-1の範囲のjの場合、do
    • matrix [i、j]が1の場合、
      • matrix [i、j]：=matrix [i、j] + matrix [i-1、j]
• 行列の各行について、
  • 行を並べ替える
  • m-1から0の範囲のjの場合、1ずつ減らします。
    • 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