Решение: Максимальная сумма подпоследовательности
Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, сумма элементов каждой из которых кратна $k=71$. Найдите среди них подпоследовательность с максимальной суммой и определите её длину. Если таких подпоследовательностей найдено несколько, укажите количество элементов самой короткой из них.
Даны два входных файла — файл А и файл B. Каждый файл содержит в первой строке количество чисел $N$ ($1 \leq N \leq 10\,000\,000$). Каждая из следующих $N$ строк содержит одно натуральное число, не превышающее $10\,000$.
Для обработки файла B не следует использовать переборный алгоритм для всех возможных вариантов, поскольку такая программа будет выполняться слишком долго.
Решение по шагам
5 шаговОбозначим через $S_i$ сумму первых $i$ элементов последовательности, где $S_0=0$. Сумма элементов подпоследовательности от $l+1$ до $r$ равна $S_r-S_l$.
$$S_r-S_l$$Эта сумма кратна $71$, если префиксные суммы имеют одинаковые остатки при делении на $71$.
$$S_r \equiv S_l \pmod{71}$$Так как все числа натуральные, при фиксированном правом конце выгодно выбирать среди префиксных сумм с нужным остатком минимальную $S_l$: тогда сумма подпоследовательности будет максимальной.
Для каждой пары одинаковых остатков сравниваем полученную сумму с текущей максимальной. Если суммы равны, выбираем меньшую длину $r-l$.
Алгоритм обрабатывает последовательность за $O(N)$ операций и использует $O(71)$ памяти, поэтому подходит для файла B.
Числовые значения для файлов А и B определяются по содержимому приложенных файлов.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары границ подпоследовательности.
Сравнивать только длины подпоследовательностей, не сравнивая их суммы.
Хранить для каждого остатка только первую позицию и не учитывать минимальную префиксную сумму.
Забыть рассмотреть префиксную сумму $S_0=0$.