给定宽度为 width 且高度为 height 的矩形网格，矩形由四个自然数 left ， right ， top 和 bottom 定义，满足：
-
left < right和top < bottom; -
left和right在范围[1, width]; -
top和bottom在[1, height]范围内 .
矩形的角是坐标为 (left, top) ， (right, top) ， (left, bottom) 和 (right, bottom) 的网格位置 .
给定矩形的整数网格，矩形的值是矩形角上网格中数字的总和 . 有一个有效的算法，给定这样的网格，找到一个具有最大值的矩形？如有必要，我们可以约束网格中的数字范围 .
蛮力算法在网格大小方面是二次方的，因为每对 (left, top) 和 (right, bottom) 有多个线性选择 . 但我想知道这个问题是否可以在线性，线性或类似的时间内解决 .
1 回答
假设网格为m×n，m≤n . 这是一个O（m2 n）时间算法 . 对于每对行（m选择2），计算它们的元素和，并考虑结果向量的两个最大条目的总和 .