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 次浏览

启动你的 职业生涯

通过完成课程获得认证

立即开始