给定一个包含 0 和 1 的 n × n 矩阵,找到最大的子矩阵 线性时间内充满 1 的矩阵。有人告诉我一个解决方案 存在 O(n) 时间复杂度。如果 n X n 中有 n^2 个元素 矩阵如何存在线性解?
除非你有子矩阵的非标准定义,否则这个问题是 NP 困难的,通过从最大派系中减少。