查找具有最大1的nXn子矩阵 [英] Find the nXn submatrix with the highest number of 1's

问题描述

我试图解决这个问题，但没有成功:

I tried to solve this question but without success:

给定3n X 3n布尔矩阵，找到O(n ^ 2)中具有最大1的nXn子矩阵.

Given 3n X 3n boolean matrix, find the nXn submatrix with the highest number of 1's in O(n^2).

我有个主意，但是是O(n ^ 3).

I had an idea but it was O(n^3).

想法:

计数矩阵中以1(0,0)开头的1，并向右移动，然后仅检查应添加的新列对VS应删除的列.下来也是一样的想法.
每次子矩阵计算都为O(n ^ 2)，而所有矩阵的传递都为O(n)，因此太多了.

count the 1's in the matrix begin with (0,0) and move to the right and check only the new col that should be added VS the col that should be deleted. And the same idea for down.
Each submatrix calculation is O(n^2) and passing all the matrix is O(n) so it's too much.

我看不到如何遍历3n X 3n矩阵(即O(n ^ 2))以及如何计算O(1)中1的数量的方法.

I don't see a way how to pass across the 3n X 3n matrix (which is O(n^2)) and also to calculate the number of 1's in O(1).

有什么想法吗?

编辑MBo:

这是原始矩阵:马提尼克斯在运行两个for循环后，CS看起来像: CS martix

This is the original matrix: The martix and after running the two for loops, CS looks like: CS martix

因此，如果您要计算从(0,0)到(1,1)的矩阵，则将是

So if you want to calculate the matrix from (0,0) to (1,1) sum will be

sum = CS[1,1] + CS[0,0] - CS[1,0] - CS[0,1] which is 2 + 1 - 2 - 1 = 0

但实际结果应该是2.

推荐答案

计算矩阵的累加和

Copy the first row of source matrix A into matrix CS

for every row except for the first one:
   for every column:
       CS[r][c] = CS[r-1][c] + A[r][c]

for every row:
   for every column except for the first one:
       CS[r][c] += CS[r][c-1]

现在，您可以找到任何右下角为y，x的子矩阵之和(省略索引为<0的加数)

Now you can find sum of any submatrix with bottom right corner at y,x (omit addends with indices < 0)

 Sum = CS[y][x] + CS[y - n][x - n] - CS[y-n][x] - CS[y][x-n]

供参考:OpenCV中的积分图像

For reference: integral image in OpenCV

import random, pprint
a = [[random.randint(0,1) for _ in range(9)] for _ in range(9)]
pprint.PrettyPrinter(indent = 2).pprint(a)
cs = [[0]*10 for _ in range(10)]
for i in range(9):
    cs[0][i] = a[0][i]
for r in range(1, 9):
    for c in range(9):
       cs[r][c] = cs[r-1][c] + a[r][c]

for r in range(9):
    for c in range(1, 9):
       cs[r][c] += cs[r][c-1]
pprint.PrettyPrinter(indent = 2).pprint(cs)

maxs = -1
for r in range(2, 9):
    for c in range(2, 9):
        s = cs[r][c] + cs[r - 3][c - 3] - cs[r -3][c] - cs[r][c-3]
        if s > maxs:
            maxs = s
            best = (r, c)
print(maxs, best)


[ [1, 1, 0, 0, 0, 1, 1, 0, 0],
  [1, 1, 0, 1, 0, 0, 0, 1, 0],
  [0, 1, 0, 1, 0, 1, 0, 1, 0],
  [0, 0, 1, 0, 1, 1, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 1, 1],
  [0, 1, 1, 0, 0, 0, 0, 0, 1],
  [1, 0, 1, 0, 0, 1, 1, 0, 1],
  [1, 1, 0, 1, 0, 1, 0, 0, 0],
  [1, 0, 0, 1, 0, 0, 1, 1, 1]]
[ [1, 2, 2, 2, 2, 3, 4, 4, 4, 0],
  [2, 4, 4, 5, 5, 6, 7, 8, 8, 0],
  [2, 5, 5, 7, 7, 9, 10, 12, 12, 0],
  [2, 5, 6, 8, 9, 12, 13, 15, 16, 0],
  [2, 5, 6, 9, 11, 14, 15, 18, 20, 0],
  [2, 6, 8, 11, 13, 16, 17, 20, 23, 0],
  [3, 7, 10, 13, 15, 19, 21, 24, 28, 0],
  [4, 9, 12, 16, 18, 23, 25, 28, 32, 0],
  [5, 10, 13, 18, 20, 25, 28, 32, 37, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

6 (4, 5)
      

这篇关于查找具有最大1的nXn子矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！