1. Идея

Нужно найти максимальный промежуток между соседними столбами, если расставить их по возрастанию координат.

Самая важная мысль: соседними считаются не столбы во входном порядке, а столбы после сортировки координат.

Значит, задача сводится к двум шагам:

1. отсортировать массив координат;
2. пройти по нему и найти максимум среди разностей a[i] - a[i - 1].

2. Наблюдения

• Пока координаты не отсортированы, нельзя понять, какие столбы являются соседними на прямой.
• После сортировки все соседние столбы будут стоять рядом в массиве.
• Тогда каждый промежуток между соседними столбами — это просто разность двух соседних элементов массива.
• Если есть одинаковые координаты, промежуток между ними равен 0. Это нормально и тоже учитывается.
• По ограничениям n до 2 * 10^5, поэтому полный перебор всех пар не подходит. Но сортировка работает достаточно быстро.

Пример:

Координаты: 7 -5 -5

После сортировки: -5 -5 7

Промежутки:

• -5 - (-5) = 0
• 7 - (-5) = 12

Максимум равен 12.

3. Алгоритм

1. Считать n.
2. Считать массив координат a.
3. Отсортировать a.
4. Инициализировать ответ как a[1] - a[0].
5. Для каждого i от 2 до n - 1:
   • вычислить a[i] - a[i - 1];
   • обновить максимум.
6. Вывести ответ.

4. Почему это работает

После сортировки координат получаем их порядок на прямой слева направо.

Пусть отсортированный массив равен a[0], a[1], ..., a[n-1].

Тогда:

• a[0] и a[1] — соседние столбы,
• a[1] и a[2] — соседние столбы,
• ...
• a[n-2] и a[n-1] — соседние столбы.

Других соседних пар нет, потому что между любыми a[i] и a[i+1] не находится ни одной другой координаты.

Значит, все нужные промежутки — это именно разности:

• a[1] - a[0]
• a[2] - a[1]
• ...
• a[n-1] - a[n-2]

Если взять максимум среди этих значений, то мы и получим самый широкий промежуток между соседними столбами.

Следовательно, алгоритм корректен.

5. Сложность

• Сортировка массива из n элементов занимает O(n log n).
• Один проход по массиву для поиска максимума занимает O(n).
• Общая сложность: O(n log n).
• Дополнительная память: O(1), если не считать память на хранение самого массива.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    long long ans = a[1] - a[0];
    for (int i = 2; i < n; i++) {
        ans = max(ans, a[i] - a[i - 1]);
    }

    cout << ans << "\n";
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

a.sort()

ans = a[1] - a[0]
for i in range(2, n):
    ans = max(ans, a[i] - a[i - 1])

print(ans)