是的,它可以做得更好。
首先,让我们考虑一个数据结构,它允许我们
O(logn)
及时 更新底层一维数组的任何单个值
O(1)
及时求出数组的最大子数组之和
实际上,如下所示的平衡二叉树可以完成这项工作。树形结构可以描述为:
- 树的每个叶节点代表数组的每个元素。
- 如果内部节点覆盖范围
[a, b]
,则其左子节点覆盖范围,其右子节点覆盖[a, c]
范围[c + 1, b]
,其中c = floor((a + b) / 2))
.
根节点覆盖 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]
。
现在让我们讨论如何使用这个数据结构找到最大矩形。如果我们将矩形的上一行和下一行固定为第 th 行i
和j
第 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)
.