给定一个大小矩阵mxn仅包含 0 和 1。我需要找到其中 1 和 0 的数量相等的最大子矩阵。蛮力方法是O(m^2*n^2)我们还能做得更好吗？
我尝试应用动态规划，但找不到任何最佳的子结构。
我相信这里讨论了这个问题的类似一维版本：
用于查找最大平衡子数组的空间有效算法？
其中有一个O(n)使用一些额外空间的解决方案。
该算法假设我们搜索具有连续行和列并且具有最大可能的高度和宽度乘积的子矩阵。
从以下预处理开始：
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
Time complexity is O(N2 * M), extra space is O(N * M).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
