最大的子矩阵为1和0等于无 [英] Largest submatrix with equal no of 1's and 0's

问题描述

由于尺寸 MXN 的基质含有0和1只。我需要找到最大的子矩阵具有相等数目的1和0中的。强力的方法是 O（平方公尺* N ^ 2）我们可以做任何比这更好的？
我试图运用动态规划，但找不到任何最优子吧。照片

Given a matrix of size mxn containing 0's and 1's only. I need to find the largest sub-matrix which has equal number of 1's and 0's in it. Brute force approach would be O(m^2*n^2) Can we do any better than this?
I tried applying dynamic programming, but couldn't find any optimal substructure to it.

我相信这个问题的一个类似的一维版本在这里进行了讨论：
<一href="http://stackoverflow.com/questions/7381050/space-efficient-algorithm-for-finding-the-largest-balanced-subarray">Space-efficient算法找到最大的平衡子阵？
其中有一个 O（N）使用一些额外的空间解决方案。

I believe a similar one-dimensional version of this problem was discussed here:
Space-efficient algorithm for finding the largest balanced subarray?
which has an O(n) solution using some extra space.

推荐答案

该算法假定我们搜索的子矩阵与连续的行和列，并与高度和宽度的最大可能的产品

This algorithm assumes that we search a sub-matrix with contiguous rows and columns and with the largest possible product of height and width.

先从以下pre-处理：

Start with the following pre-processing:

A = substitute_zero_with_minus_one(InputMatrix)
B = prefix_sum_for_each_column(A)
C = prefix_sum_for_each_row(B)

现在每对行（I，J）做如下因素：

Now for each pair of rows (i, j) do the folowing:

for each column k:
  d = C[k, j] - C[k, i]
  if h[d] not empty:
    if (k - h[d]) * (j - i) is greater than best result:
      update best result
  else:
    h[d] = k

时间复杂度为O（N ² * M），额外的空间是O（N * M）。

Time complexity is O(N² * M), extra space is O(N * M).

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