A>были бы интересны все варинаты, меньшие чем n log n, можете описать алгоритм плз

вот для массива целых чисел — от 0 до MAX_VAL.
Требуется O(MAX_VAL) дополнительной памяти. Сложность O(MAX_VAL + n).
Сортируем численным методом (MathSort) и проверяем соседние значения.

int i, j;
for (i = 0; i < MAX_VAL; i++) t[ш] = 0;
for (i = 0; i < n; i++) t[a[i]]++;
j = 1;
for (i = 0; i < MAX_VAL; i++)
while (t[i]--) a[j++] = i;

for(i = 0, m = INT_MIN; i < n-1; i++)
m = max(m,a[i+1]-a[i]);