Python 程式：查詢具有重新排列的最大子矩陣

假設我們有一個 m x n 的二進位制矩陣，我們可以以任意順序重新排列矩陣的列。我們需要找到矩陣中最大的子矩陣的面積，在執行一些重新排序任務後，子矩陣中的每個元素都是 1。

因此，如果輸入類似於

那麼輸出將是 4，因為在列交換後，我們得到如下矩陣：

這裡最大的子矩陣是大小為 4 的正方形，包含四個 1。

為了解決這個問題，我們將遵循以下步驟：

• row := 矩陣的行數，col := 矩陣的列數
• 對於 j 從 0 到 col - 1，執行
  • 對於 i 從 1 到 row - 1，執行
    • 如果 matrix[i, j] 為 1，則
      • matrix[i, j] := matrix[i, j] + matrix[i-1, j]
• ans := 0
• 對於 i 從 0 到 row - 1，執行
  • 對列表 matrix[i] 進行排序
  • 對於 j 從 col-1 到 0，遞減 1，執行
    • 如果 matrix[i, j] 等於 0，則
      • 退出迴圈
      • ans = ans 和 (col-j)*matrix[i, j]) 的最大值
• 返回 ans

示例

讓我們看看以下實現，以便更好地理解：

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

Arnab Chakraborty

更新於: 2021 年 10 月 6 日

265 次瀏覽

啟動你的 職業生涯

透過完成課程獲得認證

立即開始