解説

求めたい答えは $\displaystyle\max_{i=1,2,\dots,N}\max_{j=1,2,\dots,M}|A_i-B_j|$ です．

$|x|=\max(x,-x)$ より，答えは $\max\left(\displaystyle\max_{i=1,2,\dots,N}\max_{j=1,2,\dots,M}(A_i-B_j),\max_{i=1,2,\dots,N}\max_{j=1,2,\dots,M}(B_j-A_i)\right)$ と等しいです．

さらに，

• $\displaystyle\max_{i=1,2,\dots,N}\max_{j=1,2,\dots,M}(A_i-B_j)=\max_{i=1,2,\dots,N}A_i-\min_{j=1,2,\dots,M}B_j$
• $\displaystyle\max_{i=1,2,\dots,N}\max_{j=1,2,\dots,M}(B_j-A_i)=\max_{j=1,2,\dots,M}B_j-\min_{i=1,2,\dots,N}A_i$

であることから，結局 $\max\left(\max(A)-\min(B),\max(B)-\min(A)\right)$ を求めれば良いことが分かります．

$A,B$ の最大値・最小値はそれぞれ $O(N)$，$O(M)$ で計算できるので，この問題は $O(N+M)$ で解くことができます．