Контест Middle Массивы и хеш-таблицы спрашивают часто обновлено
Самая длинная серия подряд идущих чисел
Условие
Дан неупорядоченный массив целых чисел (могут повторяться). Найдите длину самой длинной серии значений x, x+1, …, x+L−1, которые все встречаются в массиве.
Ввод: в первой строке n (1 ≤ n ≤ 2500), во второй n чисел (|aᵢ| ≤ 10⁹).
Вывод: длина L.
Решение за O(n log n) пройдёт, но попробуйте уложиться в O(n).
Пример 1
Ввод:
7
100 4 200 1 3 2 2
Вывод:
4
Пример 2
Ввод:
1
-5
Вывод:
1
Как подойти
Подсказки: 2
- Множество отвечает «есть ли x» за O(1).
- Начинайте подсчёт только с x, у которого нет x − 1.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.