给定一个n乘n的零和1矩阵，则在线性时间内找到最大的充满1的子矩阵。有人告诉我，存在一个O（n）时间复杂度的解决方案。如果X n矩阵中有n ^ 2个元素，那么线性解如何存在？
您无法及时搜索n x n矩阵n。反例：零矩阵，其中单个元素设置为1。您必须检查每个元素以查找该元素在哪里，因此时间必须至少为O(n^2)。
n x n
n
O(n^2)
现在，如果您说矩阵有N= n^2项，并且只考虑形成连续块的子矩阵，那么您应该能够通过斜对角地穿过矩阵，找到最大的子矩阵，并随时跟踪每个矩形。通常O(sqrt(N))，您最多可以同时激活多个矩形，并且需要搜索它们以找出哪个矩形最大，因此您应该能够及时执行此O(N^(3/2) * log(N))操作。
N
n^2
O(sqrt(N))
O(N^(3/2) * log(N))
如果您可以选择任意行和列来形成子矩阵，那么我看不到任何明显的多项式时间算法。
