Решение: Поиск пары с максимальной суммой
На вход программы поступает последовательность из $n$ целых положительных чисел. Рассматриваются все пары элементов последовательности $a_i$ и $a_j$, такие что $i < j$ и $a_i > a_j$. Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на $m = 109$. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
В первой строке входных данных задаётся количество чисел $n$ ($2 \le n \le 12\,000$). В каждой из последующих $n$ строк записано одно целое положительное число, не превышающее $10\,000$. В качестве результата программа должна напечатать элементы искомой пары. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Требуется написать эффективную по времени и памяти программу для решения задачи. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности $n$ и параметра $m$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайт и не увеличивается с ростом $n$.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Решение по шагам
7 шаговОбрабатываем последовательность слева направо. Поэтому все числа, сохранённые к моменту обработки $a_j$, имеют индексы меньше $j$.
Для текущего числа $a_j$ допустимая сумма должна делиться на $109$. Если $r = a_j \bmod 109$, то предыдущий элемент должен иметь остаток $(109-r) \bmod 109$.
Для каждого остатка храним только максимальное значение среди уже обработанных чисел с этим остатком. Если это значение больше $a_j$, оно образует допустимую пару, а максимальное значение сразу даёт наибольшую сумму для текущего $a_j$.
После проверки пар текущий элемент заносится в массив максимумов для своего остатка. Это важно: иначе текущий элемент мог бы использоваться как первый элемент пары с самим собой.
Количество ячеек массива максимумов равно $109$, поэтому память не зависит от $n$. Для каждого числа выполняется постоянное число операций, поэтому время работы составляет $O(n + 109) = O(n)$.
Программа на Python 3.8:
```python
m = 109
n = int(input())
max_by_remainder = [None] * m
best_sum = -1
best_first = 0
best_second = 0
for _ in range(n):
x = int(input())
r = x % m
need = (-r) % m
first = max_by_remainder[need]
if first is not None and first > x:
current_sum = first + x
if current_sum > best_sum:
best_sum = current_sum
best_first = first
best_second = x
if max_by_remainder[r] is None or x > max_by_remainder[r]:
max_by_remainder[r] = x
print(best_first, best_second)```
Алгоритм использует массив из 109 максимумов по остаткам, работает за $O(n)$ времени и использует $O(1)$ дополнительной памяти.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Обновлять максимум для остатка до проверки текущего числа и тем самым нарушать условие $i < j$.
Не проверять условие $a_i > a_j$.
Хранить только максимальную сумму без самих элементов искомой пары.
Перебирать все пары и получать сложность $O(n^2)$.
Искать дополнительный остаток как $109-r$ без операции взятия по модулю: при $r=0$ дополнительный остаток также равен $0$.