Шешімі: Максимальная чётная сумма
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с элемента с номером $L$ и заканчивая элементом с номером $R$ включительно. Требуется найти подпоследовательность $S(L, R)$ максимальной длины, сумма элементов которой положительна и чётна. Гарантируется, что хотя бы одна такая подпоследовательность существует.
Даны два входных файла, файл A и файл B. В первой строке каждого файла содержится число $N$ ($5 \leq N \leq 10\,000\,000$), затем следуют $N$ целых чисел, каждое по модулю не превышает 1000. Для каждого файла определите длину искомой подпоследовательности. Типовой пример из условия является иллюстративным; используйте данные из приложенных файлов.
Шешім по шагам
4 қадамОбозначим префиксную сумму через $P_i=a_1+a_2+\dots+a_i$, причём $P_0=0$. Сумма подпоследовательности $S(L,R)$ равна $P_R-P_{L-1}$.
Сумма $P_R-P_{L-1}$ чётна тогда и только тогда, когда $P_R$ и $P_{L-1}$ имеют одинаковую чётность.
Для каждого текущего $R$ выбираем среди ранее встречавшихся префиксов той же чётности такой, у которого минимальная сумма. Это обеспечивает положительную разность и максимальную длину при подходящем индексе.
Алгоритм обрабатывает каждый элемент один раз, хранит минимальные префиксные суммы и соответствующие позиции для двух чётностей. Его сложность — $O(N)$ по времени и $O(1)$ по дополнительной памяти.
Ответы для файлов A и B определяются однопроходным алгоритмом по данным файлов; сами файлы в условии не представлены.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары границ подпоследовательности.
Проверять только чётность суммы, не проверяя её положительность.
Забывать префикс $P_0=0$.
Использовать тип данных, недостаточный для хранения суммы при больших $N$.