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

Question

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

11

在一个大小为NxN的矩阵中寻找最大和子矩阵可以使用二维kadane算法在O(n^3)的时间内完成，正如其他帖子中所指出的。然而，如果该矩阵是稀疏的，具体来说，只有O(n)个非零元素，那么是否可以击败O(n^3)的时间呢？

如果需要，在当前应用中，假设每行和每列中最多有一个非零值的解决方案就足够了。然而，在我的未来应用中，这种假设可能不合适（只有稀疏性成立），无论如何，我数学直觉告诉我，可能有一些好的解决方案仅利用稀疏性并且不进一步利用矩阵是对角线和排列矩阵的乘积的事实。

- user2566092

如果每行和每列最多只有一个非零值，则将这些值投影到x轴和y轴上，您将得到两个大小为n的一维数组。找到这两个数组的最大连续子数组。我认为这将给出最大的子矩形。这可以在O(n)时间和O(n)空间复杂度内完成。 - Jason L

1

不幸的是，这个提出的O(n)解决方案行不通，因为以下反例说明了： 1 0 0 0 0 2 0 -1 0 - user2566092

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fuch · Accepted Answer

是的，它可以做得更好。

首先，让我们考虑一种数据结构，它允许我们在O(logn)时间内更新底层1D数组的任何单个值，并在O(1)时间内找到数组的最大子数组之和。

实际上，下面这样的平衡二叉树可以完成这项工作。树结构可以描述为：

Every leaf node of the tree represents every element of the array.
If an internal node covers range [a, b], its left child covers range [a, c] and its right child covers range [c + 1, b], where c = floor((a + b) / 2)).

The root node covers range [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] = 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行和第j行，则问题转化为1D最大子数组和问题，其中A[k] = sum{B[i..j, k]}。关键见解是，对于一个固定的i，如果我们按升序枚举j，我们可以使用上述数据结构快速维护底层的1D数组并找到答案。下面是该想法的伪代码:

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)更好。