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) 时间内完成 maximum sum subrectangle in a sparse matrix .这击败了 Kadane 的 O(n^3) 算法。