这题用O(S^2)的算法会不会有另一种遗漏的情况

把整个牛场看成平面直角坐标系第一象限上的一部分，（0，0）就是原点，x为横，y为纵。

确定左边界之后往右枚举右边界的时候如果碰到一个纵坐标一样的怎么办？不管修改上下边界都会有遗漏吧…

请求大牛赐教。

TA201314 LV 8 @ 2015-04-21 21:42:56

不对不对，因为如果出现这种情况，实际上就意味着它不必要做左边界了，因为如果在往右以它为左边界的左边界上一定要有其他点才行，否则的话它就不是极大子矩形了。
TA201314 LV 8 @ 2015-04-21 21:34:46

对啊！！似乎那个O(S^2)的算法是有错误的！！
钱善民 LV 8 @ 2015-02-11 18:31:27

如果处在同一行，则可中止搜索（因为后面的矩形面积都是0

ID

1055

难度

分类

动态规划点击显示

标签

递交数

2106

已通过

653

通过率

31%

被复制

上传者

xiaomengxian

3 条评论