稀疏矩阵中的最大和子矩形

Question

如其他帖子所指出的,NxN可以O(n^3)使用2-d kadane算法及时查找矩阵中的最大和子矩形.但是,如果矩阵稀疏,特别是O(n)非零条目,是O(n^3)时候可以打败？

如果它有帮助,对于我感兴趣的当前应用程序,只需要一个解决方案就足以在矩阵的每一行和每一列中假定最多一个非零值.然而,在我未来的应用程序中,这个假设可能不合适(只是稀疏性会持续),无论如何,我的数学直觉是可能存在简单利用稀疏性的良好解决方案,并且不会进一步利用矩阵的事实.对角线和置换矩阵的乘积.

Answer 1

是的,它可以做得更好.

首先,让我们考虑允许我们使用的数据结构

1. O(logn)及时 更新底层1D阵列的任何单个值
2. O(1)及时找到数组的最大子数组的总和

实际上,如下所示的平衡二叉树可以完成这项工作.树结构可以描述为:

1. 树的每个叶节点都代表数组的每个元素.
2. 如果内部节点覆盖范围[a, b],则其左边的子节点覆盖范围,右边的子节点[a, c]覆盖范围[c + 1, b],其中c = floor((a + b) / 2)).

3. 根节点涵盖范围[1, n].

                         O
                       /   \
                     /       \
                   /           \
                 /               \
               /                   \
             O                       O
           /   \                   /   \
          /     \                 /     \
         /       \               /       \
       O           O           O           O
      / \         / \         / \         / \
    o     o     o     o     o     o     o     o
   A[1]  A[2]  A[3]  A[4]  A[5]  A[6]  A[7]  A[8]
   

每个节点附加4个字段v(包括叶节点和内部节点):

• S[v]:v's范围内 所有值的总和
• M[v]:v范围内 的最大子阵列总和
• L[v]:从v范围 左侧开始的最大子数组的总和
• R[v]:最大子阵列的,在右侧端部的总和v的范围

根据以上定义,我们可能会发现以下更新规则:

• 对于任何叶节点v,S[v] = A[v],M[v] = L[v] = R[v] = max{0, A[v]}
• 对于任何内部节点v及其子l和r,
  
  • S[v] = S[l] + S[r]
  • M[v] = max{M[l], M[r], R[l] + L[r]}
  • L[v] = max{L[l], L[r] + S[l]}
  • R[v] = max{R[r], R[l] + S[r]}

最后,我们可以实现开头提到的操作.

• 要进行更新A[i],我们可以在树中找到相应的叶节点,并使用上述规则更新沿其路径到根的字段.
• 最大子阵列总和很简单M[root].

现在让我们讨论如何使用此数据结构查找最大矩形.如果我们将矩形的上行和下行固定到i第jth行和第th行,问题将转变为1D最大子阵列和问题,其中A[k] = sum{B[i..j, k]}.关键的见解是,对于一个固定的i,如果我们j按升序枚举,我们可以使用上面的数据结构来维护底层的一维数组并快速找到答案.伪代码描述了这个想法:

result = 0
for i in (1, 2, ..., n)
    set all fields of the binary tree T to 0
    for j in (i, i + 1, ..., n)
        for any k where B[j, k] != 0
            T.update(k, A[k] + B[j, k])
        result = max{M[root], result}
return result

假设矩阵包含m非零元素,该算法的时间复杂度为O(mn logn).在你的情况下m = O(n),所以时间复杂度是O(n^2 logn),并且优于O(n^3).