Решение: Максимальная нечётная сумма
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с элемента с номером $L$ и заканчивая элементом с номером $R$ включительно.
Требуется найти такую подпоследовательность $S(L, R)$ максимальной длины, что сумма её элементов отрицательна и нечётна. Гарантируется, что хотя бы одна подпоследовательность требуемого вида существует.
Дано два входных файла — файл A и файл B. В первой строке каждого файла содержится число $N$ ($5 \leq N \leq 10\,000\,000$) — количество целых чисел. Каждая из следующих $N$ строк содержит одно целое число, значение которого по модулю не превышает 1000. Найдите длину искомой подпоследовательности отдельно для файла A и файла B.
Решение по шагам
5 шаговВведём префиксные суммы $P_0=0$, $P_i=a_1+a_2+\dots+a_i$. Сумма подпоследовательности от $j+1$ до $i$ равна разности $P_i-P_j$.
$$S(j+1,i)=P_i-P_j$$Разность $P_i-P_j$ нечётна тогда и только тогда, когда префиксные суммы имеют разную чётность.
Условие отрицательности суммы имеет вид $P_j>P_i$. Для каждого текущего $P_i$ нужно найти самый ранний индекс $j$ среди префиксных сумм противоположной чётности, которые больше $P_i$.
Чтобы получить максимальную длину, достаточно хранить минимальный индекс для каждого возможного значения префиксной суммы и каждой чётности, а затем обрабатывать значения справа налево или использовать структуру данных для поиска минимального индекса среди сумм, больших текущей.
Алгоритм обрабатывает каждый элемент за логарифмическое время при использовании дерева отрезков или Fenwick tree после сжатия координат. Для каждого из файлов вычисляется отдельный максимум.
Численные ответы зависят от содержимого файлов A и B.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только нечётность суммы и забывают условие отрицательности.
Ищут подпоследовательность максимальной суммы вместо максимальной длины.
Перебирают все пары границ подпоследовательностей, что невозможно при $N$ до $10\,000\,000$.
Путают индекс префиксной суммы $j$ с левой границей подпоследовательности $j+1$.