\(M=2\) の場合の答えは \(1\) です。以降は \(M>2\) の場合を考えます。

まず、動かす街頭は両端のいずれかに限定して良いです。これは、他の街頭を動かす場合と比べて両端の街頭をその位置に動かした方が最大値が確実に元の値以下になるからです。

左端の街頭を動かす場合を考えます。

左側の街頭を動かす場所は最大値を取っている街頭の区間の真ん中にするのが良いです。したがって、最大値を計算し、そこに実際に街頭を置いた場合の最大値を計算すれば良いです。

これを右端の街頭を動かす場合も同様に考えることで答えを計算することができます。

実装例(Python3)

n, m = map(int, input().split())
a = list(map(int, input().split()))
if m == 2:
    print(1)
    exit()
a.sort()
b = [a[i + 1] - a[i] for i in range(m - 1)]

def f(b):
    b = b[:-1]
    b.sort()
    val = -1 if len(b[:-1]) == 0 else max(b[:-1])
    return max(val, (b[-1] + 1) // 2)

print(min(f(b), f(b[::-1])))