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