algorithm - 在数字网格中找到具有最大角和的矩形

Question

给定一个宽度为 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) .

给定一个整数矩形网格，矩形的值是矩形角处网格中数字的总和。有没有一种有效的算法，给定这样一个网格，找到一个具有最大值的矩形？如有必要，我们可能会限制网格中数字的范围。

蛮力算法是网格大小的二次方，width * height ，因为每对有很多线性选择 (left, top)和 (right, bottom) .但我想知道这个问题是否可以在线性、线性对数或类似时间内解决。

Answer 1

假设网格为m×n且m≤n。这是一个 O(m² n) 时间算法。对于每对行(m 选择 2)，计算它们的逐元素总和，并考虑所得向量中两个最大条目的总和。