返回信息流题目描述如下：一个nxn的二维数组A，n是2的幂，设计一个算法求出max｛A[i1,j1]-A[i2,j2]}其中 i1>i2,j1>j2. 并分析算法复杂度
这个题目是我们讲分治的时候布置的，所以应该是用分治的思想做。但是我太菜了，毫无思路嘤嘤嘤，求各位大神解答
发自「贵邮」
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #94047同步于 2017/9/21
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
请教：如何求一个nxn的矩阵间两个值的最大的差值？
BruceWayne94
2017/9/21镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
有一个思路, 不是分治, 复杂度是O(n^2).
先生成一个和矩阵A一样大小的矩阵B, 其中B[i,j]存的是A矩阵从[0,0]到[i-1,j-1]的最小值.
然后遍历A矩阵,算出最大的A[i,j]-B[i,j] 就可以了.
如何算出B矩阵的值?
公式如下:B[i,j] = Min( B[i-1,j], B[i,j-1], A[i-1,j-1] )
第一行和第一列这种边界情况需要特殊处理一下.
(实际上用矩阵B有点浪费空间,用两个一维数组可以代替矩阵B)
楼上解法赞，补充一个分治的，对半切，分三种情况，i1 在右 i2在左（min/max），都在左（reduced），都在右（reduced）。
当n为1是退化到一维的简单情况（terminal）
一个一维数组就可以了。
【 在 crdcb 的大作中提到: 】
: 有一个思路, 不是分治, 复杂度是O(n^2).
: 先生成一个和矩阵A一样大小的矩阵B, 其中B[i,j]存的是A矩阵从[0,0]到[i-1,j-1]的最小值.
: 然后遍历A矩阵,算出最大的A[i,j]-B[i,j] 就可以了.
: ...................