给定一个宽度为 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)
.但我想知道这个问题是否可以在线性、线性对数或类似时间内解决。
最佳答案
假设网格为m×n且m≤n。这是一个 O(m2 n) 时间算法。对于每对行(m 选择 2),计算它们的逐元素总和,并考虑所得向量中两个最大条目的总和。
关于algorithm - 在数字网格中找到具有最大角和的矩形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27320750/