最大的子矩阵,等于1和0

Question

给定一个大小mxn仅为0和1的矩阵.我需要找到最大的子矩阵,其中包含相同数量的1和0.蛮力方法是O(m^2*n^2)我们可以做得比这更好吗？
我尝试应用动态编程,但找不到任何最佳子结构.

我相信这个问题的类似的一维版本在这里讨论:
用于寻找最大平衡子阵列的节省空间的算法？
它有一个O(n)使用一些额外空间的解决方案.

Answer 1

该算法假设我们搜索具有连续行和列的子矩阵,并且具有最大可能的高度和宽度乘积.

从以下预处理开始:

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

现在为每对行(i,j)执行以下操作:

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).