求一个子矩形中的最大和NxN矩阵可以完成O(n^3)正如其他帖子中指出的，使用 2-d kadane 算法的时间。然而，如果矩阵是稀疏的，具体来说O(n)非零条目，可以O(n^3)时间被打败了吗？
如果有帮助的话，对于我感兴趣的当前应用程序，有一个解决方案就足够了，该解决方案假设矩阵的每一行和每一列中最多有一个非零值。然而，在我未来的应用中，这个假设可能不合适（只有稀疏性才成立），无论如何，我的数学直觉是，可能存在简单地利用稀疏性并且不进一步利用矩阵是这样的事实的良好解决方案对角线和置换矩阵的乘积。
是的，它可以做得更好。
首先，让我们考虑一个数据结构，它允许我们
- 更新底层一维数组的任何单个值
O(logn) time
- 求数组中最大子数组的和
O(1) time
实际上，如下所示的平衡二叉树就可以完成这项工作。树结构可以描述为：
- 树的每个叶节点代表数组的每个元素。
- 如果内部节点覆盖范围
[a, b]，它的左孩子覆盖范围[a, c]及其右孩子覆盖范围[c + 1, b], where c = floor((a + b) / 2)).
-
根节点覆盖范围[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的范围
-
M[v]： 中的最大子数组和v的范围
-
L[v]：从左侧开始的最大子数组的总和v的范围
-
R[v]: 右侧结束的最大子数组之和v的范围
根据以上定义，我们可以发现以下更新规则：
- 对于任意叶节点
v, S[v] = A[v], M[v] = L[v] = R[v] = max{0, A[v]}
- For any internal node
v and its children l and 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].
现在让我们讨论如何使用这个数据结构找到最大矩形。如果我们将矩形的上行和下行固定为ith and 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).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
