algorithm - 找到包含最多 "conflicting pairs"的 m 乘 m 方格？

Question

二维平面上有两种类型的单位，绿色单位 (G) 和红色单位 (R)。 平面表示为一个n×n的矩阵，每个单元表示为矩阵中的一个元素。

如果两个单元的颜色不同，则称为“冲突对”。目标是找到包含最多“冲突对”的 m 乘 m 子矩阵。

例子

[R R 0 0 0
 R R 0 0 0
 0 0 R R 0
 0 0 0 G G
 0 0 0 G G]

在上面的5×5矩阵中，“最冲突”的3×3子矩阵位于右下角，其中有两个红色单元和四个绿色单元，子矩阵中有8个冲突对。

---

一个简单的解决方案将花费 O(m^2n^2) 来迭代每个可能的子矩阵中的每个元素。 我还想过使用像 Summed-area table 这样的动态规划。算法，时间复杂度将是 O(n^2)，这看起来不错，因为扫描每个元素一次已经是 O(n^2)。

然而，n×n 矩阵可能很大且稀疏，并且以稀疏格式(如 CSR)给出，在这种情况下，O(n^2) 算法可能效率不高。关于如何更好地处理稀疏矩阵(和密集矩阵)的任何建议？

Answer 1

如果您有 k 个非空单元格(使用 R 或 G)，那么您可以用时间复杂度 O( k^2)(压缩矩阵)因为最优子矩阵在矩阵的边界上有一个非空单元格。

或者时间复杂度可能是 O(k * (log n)^2) 如果使用二维稀疏线段树在矩形上求和。