Решение: Максимальная сумма подпоследовательности
Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна $k = 53$. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество чисел $N$ ($1 \leq N \leq 10\,000\,000$). Каждая из следующих $N$ строк содержит одно натуральное число, не превышающее $10\,000$.
Пример организации исходных данных во входном файле:
$7, 1, 3, 4, 43, 8, 5, 95$.
Для указанных входных данных при $k = 50$ искомая длина последовательности равна 2.
В ответе укажите два числа: значение длины искомой подпоследовательности сначала для файла А, затем для файла В.
Для обработки файла В не следует использовать переборный алгоритм для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение по шагам
5 шаговВведём префиксные суммы $S_i = a_1 + a_2 + \ldots + a_i$, причём $S_0 = 0$.
Сумма подпоследовательности от $l$ до $r$ равна $S_r - S_{l-1}$. Она кратна $53$, если $S_r$ и $S_{l-1}$ имеют одинаковые остатки при делении на $53$.
Так как все числа натуральные, при фиксированном остатке выгодно рассматривать минимальную и максимальную префиксные суммы. Разность максимальной и минимальной сумм даёт максимальную сумму подходящей подпоследовательности.
Если максимальная сумма получается несколькими способами, сравниваем длины соответствующих отрезков и выбираем минимальную.
Для каждого файла достаточно одного прохода по данным и хранения информации для 53 остатков, поэтому сложность обработки равна $O(N)$, а дополнительная память — $O(53)$.
Числовые ответы невозможно определить без содержимого файлов А и В.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары границ подпоследовательности.
Сравнивать только длины подпоследовательностей, не максимизируя сначала сумму.
Использовать одинаковый остаток только для соседних префиксных сумм.
Не учитывать правило выбора самой короткой подпоследовательности при равенстве максимальных сумм.