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

Question

使用二维 kadane 算法可以在 O(n^3) 时间内找到 NxN 矩阵中的最大和子矩形，如其他帖子中所指出的.但是，如果矩阵是稀疏的，特别是 O(n) 非零项，O(n^3) 时间能否被打败？

如果它有帮助，对于我感兴趣的当前应用程序，有一个在矩阵的每一行和每一列中最多假设一个非零值的解决方案就足够了。然而，在我 future 的应用中，这个假设可能不合适(只是稀疏性会成立)，而且无论如何我的数学直觉是可能有很好的解决方案只是利用稀疏性而不进一步利用矩阵是对角线和置换矩阵的乘积。

Answer 1

是的，它可以做得更好。

首先，让我们考虑一个数据结构，它允许我们

1. 在O(logn) 时间内更新底层一维数组的任何单个值
2. 在O(1) 时间内找到数组的最大子数组之和

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

1. 树的每个叶节点代表数组的每个元素。
2. 如果一个内部节点覆盖范围[a, b]，它的左 child 覆盖范围[a, c]，它的右 child 覆盖范围[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]
   

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

• S[v]:v范围内所有值的总和
• M[v]:v范围内的最大子数组和
• L[v]:从v范围左侧开始的最大子数组之和
• R[v]:结束于v范围右侧的最大子数组之和

根据以上定义，我们可以发现如下更新规则:

• 对于任何叶节点v，S[v] = A[v]，M[v] = L[v] = R[v] = 最大值{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 和第 j 行，问题就变成了一维最大子数组和问题，其中 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).