Python中通过列重排来查找最大子矩阵面积的程序

Python中通过列重排来查找最大子矩阵面积的程序

假设我们有一个二进制矩阵。我们可以随意重排列,然后找到包含1的最大子矩阵的面积。

所以,如果输入如下:

1 0 0
1 1 1
1 0 1

那么输出将为4,因为我们可以像这样排列:

1 0 0
1 1 1
1 1 0

为了解决这个问题,我们将按以下步骤进行:

  • 将n赋给矩阵的行数
  • 将m赋给矩阵的列数
  • 将ans赋给0
  • 对于i在1到n-1的范围内,执行以下操作
    • 对于j在0到m-1的范围内,执行以下操作
      • 如果matrix[i,j]是1,则
      • 将matrix[i,j]的值设为matrix[i,j] + matrix[i-1,j]
  • 对于矩阵中的每一行执行以下操作
    • 对该行进行排序
    • 对于j在m-1到0的范围内,递减1执行以下操作
      • ans设为ans和row[j] * (m – j)的最大值
  • 返回ans

示例

让我们查看以下实现以更好地理解

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程