我试图计算一个大的2D输入的最大曼哈顿距离，输入由（x，y）s组成，我想做的是计算这些坐标之间的最大距离在不到O（n^2）的时间内，我可以通过遍历所有元素来在O（n^2）中做到这一点，比如：
*（两点 （X1，Y1） 和 （X2，Y2） 之间的曼哈顿距离为 ： |X1-X2|+ |Y1-Y2|）
for ( 0 -> n )
for ( 0-> n )
{ // here i calculate |Xi - Xj| + |Yi - Yj| which is maximum }
但是对于非常大的输入，它不会有效地工作，:(
任何人都对更好的算法有任何想法？
只有两种情况需要考虑，如果我们只考虑这样的结果。Xi <= Xj
Yi <= Yj(Xj + Yj) - (Xi + Yi)
(Xj - Yj) - (Xi - Yi)
通过将其分解为这些情况，我摆脱了绝对值函数，使其更容易推理距离。
因此，我们只需选择具有最小值和最大值的点，然后计算距离。然后选取具有最小值和最大值的点，并计算距离。这两个距离中的一个是您的最大值。x+yx-y
这可以在 中完成，这是渐近最优的。O(n)
它相当简单，可以计算在O(n)
让和x1>x2y1>y2
max(|x1-x2|+|y1-y2|) = max(x1-x2+y1-y2) = max(x1+y1) - min(x2+y2)
让和x1>x2y1<y2
max(|x1-x2|+|y1-y2|) = max(x1-x2-y1+y2) = max(x1-y1) - min(x2-y2)
现在，将 x1 更改为 x2，您将获得相同的结果。
因此，一般来说，您的解决方案是
max ( (max(xi+yi)-min(xi+yi)), (max(xi-yi) - min(xi-yi)) )
