algorithm - 子矩阵 NxN 矩阵和具有 N 个非零值的最大和，仅 O(N^2)

Question

假设您有一个 N × N 矩阵，其中每一行正好有一个非零元素，每一列正好有一个非零元素（非零元素可以是正数或负数）。我们想找到最大和子矩阵。我们这样做的效率如何？

该矩阵的维度为 N × N，并且只有 N 个非零元素。N 太大了，所以我不能使用 O(N ³ ) 算法。有谁知道如何在 O(N ² )、O(N log N) 或其他类似的时间复杂度上解决这个问题？

谢谢！

Answer 1

如果你想找到最大和子矩形，你可以在 O(n^2 log n) 时间内使用这里描述的算法在稀疏矩阵中最大和子矩形。这击败了 Kadane 的 O(n^3) 算法。