Шешімі: Максимальная сумма подпоследовательности
Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна $k = 97$. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел $N$ ($1 \leq N \leq 10\,000\,000$). Каждая из следующих $N$ строк содержит одно натуральное число, не превышающее $10\,000$.
Пример организации исходных данных во входном файле:
$7, 1, 3, 4, 93, 8, 5, 95$.
Для указанных входных данных при $k = 50$ искомая длина последовательности равна $2$.
В ответе укажите два числа: значение длины искомой подпоследовательности сначала для файла A, затем для файла B.
Для обработки файла B следует использовать алгоритм, работающий за линейное время, а не перебор всех возможных подпоследовательностей.
Шешімін қадамдап көрсету
5 қадамВведём префиксные суммы $S_0 = 0$ и $S_i = a_1 + a_2 + \dots + a_i$. Сумма подпоследовательности от позиции $l$ до позиции $r$ равна $S_r - S_{l-1}$.
Сумма будет кратна $97$, если $S_r \bmod 97 = S_{l-1} \bmod 97$. Поэтому для каждого остатка нужно рассматривать префиксные суммы с одинаковым остатком.
Так как все числа натуральные, для каждого остатка достаточно хранить минимальную встреченную префиксную сумму и её позицию. Она даёт максимальную разность $S_r - S_{l-1}$ для текущей правой границы.
При равенстве максимальных сумм сравниваем длины подпоследовательностей и сохраняем меньшую. Алгоритм обрабатывает каждый элемент один раз и использует $97$ групп остатков.
Точные два числовых результата можно получить только после обработки содержимого файлов A и B, которые в условии не предоставлены.
Числовые значения для файлов A и B невозможно определить без самих входных файлов.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары границ подпоследовательности, получая квадратичную сложность.
Хранить для остатка максимальную, а не минимальную префиксную сумму.
Забывать префиксную сумму $S_0 = 0$.
При равной максимальной сумме выбирать первую найденную подпоследовательность вместо самой короткой.