Pythonで許可されている列の交換で1の最大の長方形を見つけます

バイナリ行列があるとすると、その与えられた行列内のすべての1の中で最大の長方形を見つける必要があります。長方形は、その行列の列の任意のペアを交換または交換することで作成できます。

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

この場合、出力は6になります。長方形は、列1を3と交換することで生成できます。交換後の行列は、-

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

• 行：=マットのサイズ

• col：=マットのサイズ[0]

• temp：=次数（行+ 1）x（列+ 1）の行列、0で埋める

• 0からcolの範囲のiの場合、実行

  • temp [0、i]：=mat [0、i]

  • 1から行までの範囲のjについては、次のようにします

    • mat [j、i]が0と同じ場合、

      • temp [j、i]：=0

    • それ以外の場合

      • temp [j、i]：=temp [j-1、i] + 1

• 0から行までの範囲のiの場合、実行

  • cnt：=サイズ（行+ 1）の配列で、0で埋められます

  • 0からcolの範囲のjの場合、1ずつ増やします。

    • cnt [temp [i、j]]：=cnt [temp [i、j]] + 1

  • col_no：=0

  • j：=行

  • j> =0の場合、実行

    • cnt [j]> 0の場合、

      • 0からcnt[j]の範囲のkの場合、実行

        • temp [i、col_no]：=j

        • col_no：=col_no + 1

    • j：=j-1

• area_maximum：=0

• 0から行までの範囲のiの場合、実行

  • 0からcolの範囲のjについては、次のようにします

    • area_current：=（j + 1）* temp [i、j]

    • area_current> area_maximumの場合、

      • area_maximum：=area_current

• area_maximumを返す

例

理解を深めるために、次の実装を見てみましょう-

def maxArea(mat):
   row = len(mat)
   col = len(mat[0])
   temp = [[0 for i in range(col + 1)] for i in range(row + 1)]
   for i in range(0, col):
      temp[0][i] = mat[0][i]
   for j in range(1, row):
      if ((mat[j][i] == 0)):
         temp[j][i] = 0
      else:
         temp[j][i] = temp[j - 1][i] + 1
   for i in range(0, row):
      cnt = [0 for i in range(row + 1)]
      for j in range(0, col, 1):
         cnt[temp[i][j]] += 1
      col_no = 0
      j = row
      while(j >= 0):
         if (cnt[j] > 0):
            for k in range(0, cnt[j]):
               temp[i][col_no] = j
               col_no += 1
         j -= 1
   area_maximum = 0
   for i in range(0, row):
      for j in range(0, col):
         area_current = (j + 1) * temp[i][j]
         if (area_current > area_maximum):
            area_maximum = area_current

   return area_maximum
mat = [
   [0, 0, 1, 1, 0],
   [0, 0, 1, 1, 1],
   [1, 0, 1, 1, 0]]
print("Area : ",maxArea(mat))

入力

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

出力

Area : 2