我们考虑将题目所求的 曼哈顿距离 转化为 切比雪夫距离，即把每个点的坐标 $(x, y)$ 变为 $(x + y, x - y)$。

所求的答案就变为 $\max \begin{Bmatrix} \max\begin{Bmatrix} \left | x_i - x_j\right| ,\left | y_i - y_j\right| \end{Bmatrix} \end{Bmatrix}$ 。

在所有点中，横坐标之差的最大值和纵坐标之差的最大值都有可能成为答案，所以我们只需要预处理出 $x, y$ 的最大值和最小值即可。时间复杂度为 $O(n)$ 。

来源：https://heartlessly.github.io/problems/bzoj-3382/