algorithm - 等于 1's and 0' s 的最大子矩阵

Question

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

我相信这里讨论了这个问题的类似一维版本:
Space-efficient algorithm for finding the largest balanced subarray?
它有一个使用一些额外空间的 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)。