Обработка серий

Серия — это подряд идущая группа элементов последовательности, обладающих одним признаком. В задачах требуется найти длину самой длинной серии, количество серий, их суммарную длину или другие характеристики; те же алгоритмы применяются к массивам и строкам.

Что такое серия

Серия образуется соседними элементами, для которых выполняется один и тот же признак: например, \(a_i > 0\), \(a_i = 5\), символ является буквой или два соседних числа равны. Серии разделяются элементами, не удовлетворяющими признаку. Если последовательность рассматривается как обработка последовательности, то серия — один из основных объектов подсчёта.

Если нужно найти максимальную серию, после каждого увеличения обновляют максимум. Подробное понятие максимальной серии разобрано на странице «Максимальная серия»; здесь сосредоточимся на общем шаблоне.

Два способа обработки

Есть два равноправных подхода. В первом для каждого элемента поддерживается длина текущей серии. Такой способ удобен, если нужен максимум, количество серий или сумма длин. Во втором серия обрабатывается целиком: находим её начало, затем последовательно пропускаем все элементы с тем же признаком.

• Счётчик текущей серии: при выполнении признака увеличиваем \(cur\), иначе присваиваем \(cur=0\).
• Переходы: новая серия начинается, когда текущий элемент удовлетворяет признаку, а предыдущий — нет.
• Границы: после цикла иногда нужно отдельно обработать серию, которая заканчивается последним элементом.
• Для строк признаком может быть условие s[i] == 'A', s[i].isdigit() или принадлежность заданному набору символов.

Количество и длина серий

Количество серий считают по началу каждой серии. Если элементы идут слева направо, серия начинается в позиции \(i\), когда \(P(a_i)\) истинно и либо \(i\) — первый индекс, либо \(P(a_{i-1})\) ложно. Это соответствует теме количество серий, которую полезно изучить заранее.

Квадратные скобки обозначают индикатор: он равен \(1\), если условие истинно, и \(0\) в противном случае. Если нужно найти сумму длин всех серий, достаточно считать количество элементов, удовлетворяющих признаку: каждый такой элемент входит ровно в одну серию.

Универсальный алгоритм

Пусть дана последовательность \(a_1,\ldots,a_n\) и признак \(P\). Перебираем элементы слева направо. При истинном признаке увеличиваем текущую длину, при ложном — завершаем серию и обнуляем счётчик. В зависимости от задачи в момент завершения можно обновить минимум, максимум, сумму или число элементов.

1cur = 0
2best = 0
3series = 0
4for x in a:
5    if P(x):
6        if cur == 0:
7            series += 1
8        cur += 1
9        best = max(best, cur)
10    else:
11        cur = 0

В Python условие P(x) заменяется конкретным выражением, например x > 0. В Паскале и C++ логика та же: важны не названия переменных, а порядок обновления состояния.

Разобранный пример

Дана последовательность: \(-2, 5, 7, 3, -1, 4, 6, -8, 9\). Найдём длину максимальной серии положительных чисел, количество таких серий и длину последней серии.

Серии в строках

Строку можно рассматривать как массив символов — см. страницу «Строка как массив символов». Например, в строке aaabbcaa серии одинаковых символов имеют длины \(3,2,1,2\). Для такого случая признак задаётся не отдельно для каждого символа, а сравнением с предыдущим: серия продолжается, если s[i] == s[i-1].

Другой вариант — серии символов одного класса: цифр, латинских букв, пробелов или символов из заданного набора. Тогда сначала определяют функцию-признак, а затем применяют тот же счётчик. При необходимости выделить фрагмент строки пригодятся срезы строки и приём обработки строки по символам.

Другие характеристики серий

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

1. Сначала определить признак серии и то, в какой момент серия завершается.
2. Завести cur и переменные результата с безопасными начальными значениями.
3. При каждом элементе изменить cur согласно признаку.
4. При завершении серии обновить характеристики; после цикла обработать незавершённую последнюю серию.