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