Задача в Пайтон (python) Вам дан список песен, которые до сих пор играли на радио 106 FM. Всего в списке содержится N песен. Найти продолжительность самого длинного фрагмента песен, состоящего из неповторяющихся песен. Входные данные: В первой строке одно целое число N – количество песен, в следующей строке N целых чисел, 1, 2, . . . , N – каждой песне присваивается идентификационный номер. Выходные данные: Выведите длину самого длинного неповторяющегося фрагмента песни. Пример: Вход: 8 1 2 1 3 2 7 4 2 Выход: 5

Задача сводится к поиску самой длинной непрерывной последовательности песен, в которой все идентификаторы различны.

Эффективный способ решения — метод скользящего окна (two pointers).

Заведём два указателя: левый L и правый R, оба сначала равны 0, и множество для хранения встреченных номеров.

Будем двигать R вправо, добавляя номера песен в множество.

Если очередной номер уже есть в множестве, значит, появился повтор — тогда сдвигаем L вправо, удаляя номера из множества, пока повтор не исчезнет.

На каждом шаге длина текущего окна без повторов равна \( R - L + 1 \), запоминаем максимальную.

Алгоритм работает за \( O(N) \) и не требует вложенных циклов.

Для примера с последовательностью 1 2 1 3 2 7 4 2 самый длинный фрагмент без повторов — 1 3 2 7 4 (длина 5).

0 0 Пожаловаться